[fpc-pascal] Re: TimSort

[Mattias Gaertner]

On Wed, 25 May 2011 09:02:46 +0200 (CEST)
marcov at stack.nl (Marco van de Voort) wrote:

> In our previous episode, Mattias Gaertner said:
> >  > A quick look at wikipedia will show that timsort has a disadvantage too. It
> >  > needs up to N records memory, not just Log(n) records like e.g. Quicksort.
> >  It *can* be implemented to need only log(n). But the current fpc implementation
> > of QuickSort seems to need O(n) memory on the stack.
> 
> Hmm. Then that should be fixed.

It must choose the smaller half for the tail call.

  
> >  TimSort needs up to N/2 pointer, which is better than a simple MergeSort.
> 
> For heavier sorting I usually use heapsort and quicksort routines that date
> back to my M2 days
> 
> Usually heapsort since it is quite fast for already sorted collections.

Yes, but Heapsort is not stable too.

Mattias