nc-gaertnma at netcologne.de
Tue May 24 20:25:07 CEST 2011
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
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
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
More information about the fpc-pascal