Sign in Join

Live chat for Free Pascal, Lazarus, Delphi and every Pascal programmer.

Mailing lists / lazarus / 2009-08

Sorting, mergesort and quicksort

6 messages · 5 people · –

Reply by email Subscribe to this list Your subscription

Read-only archive. Use j and k to move between messages.

Santiago A.

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.

Santiago A.

Reply by email

Mattias Gärtner
to Santiago A.

Zitat von "Santiago A." :

Show quoted text 13 lines
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

Reply by email

Marco van de Voort
to Mattias Gärtner: Zitat von "Santiago A." : The runtime of Quicksort depends on the pivot element. The FCL…
Mattias G??rtner wrote 18 lines
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.

Reply by email

Mattias Gaertner
to Marco van de Voort
Show quoted text 8 lines
[...] > 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.

True, although heapsort jumps much more around than quick/mergesort, so you get a lot of cache misses.

Mattias

Reply by email

Marco van de Voort
to Mattias Gaertner
Mattias Gaertner wrote 11 lines
>[...] > > 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. True, although heapsort jumps much more around than quick/mergesort, so you get a lot of cache misses.

While classically true, nowdays the items to be sorted are allocated dynamically, and they probably are not consequtive in memory anyway.

Reply by email