[fpc-pascal] TimSort

[Mattias Gaertner]

On Tue, 24 May 2011 19:53:12 +0200
José Mejuto <joshyfun at gmail.com> wrote:

> Hello FPC-Pascal,
> 
> Tuesday, May 24, 2011, 6:31:56 PM, you wrote:
> 
> MG>  It uses a lot of tricks, but it seems to me that Tim explained all the
> MG> important things.
> MG>  It would be nice, if thetimsort unit has the same license as the FCL (modified
> MG> LGPL-2).
> MG>  Maybe you can ask him for permission.
> MG>  The c implementation uses some ugly macros, but the rest should be easily
> MG> translated to pascal.
> 
> I'm now implementing from scratch, maybe it will not be the "fastest"
> implementation but I hope that at least works :) After partial
> implemenation it looks like a combination of insertion sort for small
> runs and mergesort to combine the already sorted runs.

Yes, and some more tricks. You should read
http://svn.python.org/projects/python/trunk/Objects/listsort.txt

If you do only the insertion+mergesort, then you have only implemented
a long known improved mergesort variant and you can not call it
TimSort. Of course then you don't need to ask Tim for permission.

 
> Anyway it looks to need O(n) auxiliary storage, where O could be a
> pointer.

Read Tim's text: N/2 pointer, so on a 32bit system 2*N byte.

 
> Implementing from paper needs permission to licensing ? Is the algo
> copyrighted/patented ?

IMO it is simply good manner to ask Tim. 
He spent quite some time in testing and tuning and explained the
algorithm in detail, so I guess he will be happy to see his fame
spreading.


Mattias