Re: [fpc-pascal] Re: TimSort
On Wed, 25 May 2011 09:29:09 +0200 Mattias Gaertner nc-gaert...@netcologne.de wrote: 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. I created a patch. http://bugs.freepascal.org/view.php?id=22119 Mattias ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Re: TimSort
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. ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Re: TimSort
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
Re: [fpc-pascal] Re: TimSort
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. ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Re: TimSort
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
