Marco van de Voort <mar...@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
_______________________________________________
fpc-pascal maillist - fpc-pascal@lists.freepascal.org
http://lists.freepascal.org/mailman/listinfo/fpc-pascal