On Tue, 24 May 2011 19:53:12 +0200 José Mejuto <joshy...@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 _______________________________________________ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal