[Lazarus] Sorting, mergesort and quicksort

[Marco van de Voort]

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.