On Fri, Aug 21, 2009 at 01:59:25PM +0200, Mattias G??rtner wrote: > The runtime of Quicksort depends on the pivot element. The FCL > implementation uses the middle element, which is good for partly > sorted data and bad for random data. It needs in worst case O(n*n). > If you want a worst case runtime of O(n*logn) like MergeSort then you > can use the complicated Select algorithm, but this requires extra > memory. > So quicksort is normally somewhat faster than mergesort it can be > easily 10 times slower even on only 1000 elements. > > Both QuickSort and MergeSort can be used for linked lists. > > The extra memory of mergsort is one pointer per element, not a > duplicate of the whole data. > > Btw, there is a new kid in town: ParallelSort. > This uses a parallel mergesort and automatically uses several threads. > See here: > http://wiki.lazarus.freepascal.org/Parallel_procedures#Example:_parallel_sort
Classically people used heapsort for lists that were possibly already sorted. It's inplace, but not stable and O(n*log(n)) iirc. -- _______________________________________________ Lazarus mailing list [email protected] http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
