[Lazarus] Sorting, mergesort and quicksort

[Marco van de Voort]

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.