[Lazarus] Sorting, mergesort and quicksort

Marco van de Voort marcov at stack.nl
Tue Aug 25 22:20:48 CEST 2009


On Tue, Aug 25, 2009 at 10:14:12PM +0200, Mattias Gaertner wrote:
> >[...]
> > > 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.




More information about the Lazarus mailing list