Front page | perl.perl5.porters |
Postings from September 2013
2013/9/6 John P. Linderman <jpl.jpl@gmail.com> > The only sequences (that I could think of, anyway) where it was clear that > qsort would outperform merge sort were those containing many repetitions of > a small number (k) of keys. Qsort's "fat pivot" guaranteed that only k > passes would be required, where merge sort might need log N. > Seems memory usage can be better with qsort than with mergesort (not sure about perl implementation). http://en.wikipedia.org/wiki/Merge_sort === Merge sort's most common implementation does not sort in place; therefore, the memory size of the input must be allocated for the sorted output to be stored in (see below for versions that need only *n*/2 extra spaces). === http://en.wikipedia.org/wiki/Quicksort === The disadvantage of the simple version above is that it requires O(*n*) extra storage space, which is as bad as merge sort<http://en.wikipedia.org/wiki/Merge_sort>. The additional memory allocations required can also drastically impact speed and cache performance in practical implementations. There is a more complex version which uses an in-place<http://en.wikipedia.org/wiki/In-place_algorithm>partition algorithm and can achieve the complete sort using O(log *n*) space (not counting the input) on average (for the call stack<http://en.wikipedia.org/wiki/Call_stack>). We start with a partition function: ===Thread Previous | Thread Next