[fpc-pascal] TimSort

José Mejuto joshyfun at gmail.com
Tue May 24 20:31:33 CEST 2011

Hello FPC-Pascal,

Tuesday, May 24, 2011, 8:25:07 PM, you wrote:

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

Well, in first "try" I'm implementing the Insert+Merge, them refine
with galloping and some other conditions :)

>> Anyway it looks to need O(n) auxiliary storage, where O could be a
>> pointer.
MG> Read Tim's text: N/2 pointer, so on a 32bit system 2*N byte.

I had read it, but I do not understand it :( specially the "2*N byte"
because in the paper he states that it requieres much more, specially
in auxiliary storage for merge sort, not counting the stack for the
runs or the auxiliary copy for one insertion sort pointer.

Anyway I'll read it again, maybe something escapes my english skills
>> Implementing from paper needs permission to licensing ? Is the algo
>> copyrighted/patented ?
MG> IMO it is simply good manner to ask Tim.
MG> He spent quite some time in testing and tuning and explained the
MG> algorithm in detail, so I guess he will be happy to see his fame
MG> spreading.

I'll e-mail him anyway. Netiquete :)

Best regards,

More information about the fpc-pascal mailing list