On Wed, 25 May 2011 09:02:46 +0200 (CEST) mar...@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 _______________________________________________ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal