[fpc-pascal] Re: TimSort

Marco van de Voort marcov at stack.nl
Wed May 25 09:02:46 CEST 2011

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

More information about the fpc-pascal mailing list