[Lazarus] Sorting, mergesort and quicksort

[Mattias Gärtner]

Zitat von "Santiago A." <svaa at ciberpiula.net>:

> Hello:
>
> Just a question. I've been lurking  the source of LCL and I've seen that
> in many places (gtk, files and others...) to sort lists uses mergesort.
>
> As far as I know, mergesort is used for sorting data with sequential
> access, or when random access is expensive. It needs to copy the
> original data, so it needs double memory.
>
> I can understand thet mergesort be used for linked lists, where you
> can't jump from position 30 to 1 without moving to 29..28..27 etc , but
> in Lazarus is used for standard arrays where quicksort shines. In fact,
> I've seen that Lazarus uses in quicksort many times.

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


Mattias