cef@cmu-cs-spice.ARPA (Charles Fineman) (06/11/85)
Of course, in the general case there is no algorithim that will take advantage of the fact that the keys are already sorted by F1:F2. However, in certain configurations, it may be possible to improve the performance of a MERGE sort (see Wirth A+D=P) but usually not by very much. The assumption is that for at least some (at best most) values of F1 have serveral values of F2 associated with it. More clearly stated, say F1 is a persons last name and F2 is the persons first name. If the index is a phone book, you will ususally have several first name entries for each last name entry. Using this assumption, you may be able to come up with a new MERGE sort that will have an better performance than a standard sort. My intuition is that the performance will improve only by a constant factor or from O(f(n)) to O(f(n-m)) where f is the performace function of the original MERGE sort. ~Chaz Bah | Have Walkman, will travel (but I prefer to ride). | | Everybody must get stoned!