[fpc-pascal] Re: TimSort

[Mattias Gaertner]

On Wed, 25 May 2011 09:29:09 +0200
Mattias Gaertner <nc-gaertnma at netcologne.de> wrote:

> 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.

I created a patch.

http://bugs.freepascal.org/view.php?id=22119

Mattias