Zitat von "Santiago A." <[email protected]>:
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
--
_______________________________________________
Lazarus mailing list
[email protected]
http://lists.lazarus.freepascal.org/mailman/listinfo/lazarus
