[fpc-pascal] Re: TimSort

[Mattias Gaertner]

 Marco van de Voort <marcov at stack.nl> hat am 24. Mai 2011 um 18:53 geschrieben:

 > In our previous episode, Uffe Kousgaard said:
 > > > Why is TimSort specially interesting to you ?
 > >
 > > If it is the best all-purpose sorting algorithm and now the standard in
 > > several other programming languages, it should be obvious why it is also
 > > worth looking at for pascal / delphi developers.
 >
 > 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.

 TimSort needs up to N/2 pointer, which is better than a simple MergeSort.

 Mattias
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freepascal.org/pipermail/fpc-pascal/attachments/20110524/8b2ccf49/attachment.html>