Front page | perl.perl5.porters |
Postings from June 2004
In article <40E2774F.1070106@perltraining.com.au>, Paul Fenwick <pjf@perltraining.com.au> writes: > I haven't thought about any other sorting algorithms yet. I agree that > heapsort is definitely worth examining as an efficient way to gathering > only the first sorted M elements, as at each stage the next element is > known (the root), and there are only two choices for the next element > (the immediate children of the root). > Mergesort works well too if you cut off runs at M. you start with N/M groups of M elements, each sort in O(MlogM), so that gives (NlogM). Then you need to combine N/M runs, which is (N/M-1) combines, in which each can stop after collecting M elements => O(N). So the sum is still O(NlogM) And since the plain sort already is mergesort, i think that would be the best choice since it will e.g. have the same stability properties, and the partial sort smoothly extends to the full sort.