Don Baccus <dhogaza@pacifier.com> writes:
>> For example, if you want the 10 best rows from 100000, these are the
> average numbers of comparisons:
>>
>> QuickSort: 1.6E+14
>> SortStop: 1.5E+11
Are there some zeroes missing here? That sounds like an awful lot of
operations for a quicksort of only 1E5 elements...
> This makes sense ... you can stop once you can guarantee that the first
> ten rows are in proper order. I'm not familiar with the algorithm
> but not terribly surprised that one exists.
The obvious way to do it would be with a heap-based sort. After you've
built the heap, you pull out the first ten elements and then stop.
Offhand this only seems like it'd save about half the work, though,
so maybe Roberto has a better idea.
regards, tom lane