I am fairly new to Python and am attempting to write a timsort re-implementation. While writing the program I have had trouble working out how to get the minrun length. The sources I have consulted have described identifying minrun as:
minrun = N/minrun<=2^N where n is the size of the array.
I understand what I am trying to do, I just dont know how i could do it in Python?
Any ideas or sample code would be very useful, thanks!
In the wikipedia trimsort-article the built in implementation of the python timsort is described:
Minrun is chosen from the range 32 to 64 inclusive, such that the size of the data, divided by minrun, is equal to, or slightly less than, a power of two. The final algorithm takes the six most significant bits of the size of the array, adds one if any of the remaining bits are set, and uses that result as the minrun. This algorithm works for all arrays, including those smaller than 64; for arrays of size 63 or less, this sets minrun equal to the array size and Timsort reduces to an insertion sort.
You could do it like this:
minrun = length
remaining_bits = length.bit_length() - 6
if remaining_bits > 0:
minrun = length >> remaining_bits
mask = (1 << remaining_bits) - 1
if (length & mask) > 0: minrun += 1
That should be it, for any other timsort questions make sure to take a look at the the python timsort.