[fpc-pascal] Re: TimSort
nc-gaertnma at netcologne.de
Thu May 24 19:35:22 CEST 2012
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.
More information about the fpc-pascal