CODEWITHSUNDEEP
pythonjavasortingmergesorttimsort
natisaver
natisaver

Reputation: 79

How is TimSort Minimum Run Length Determined?

I found this implementation of generating a value of minimum run size for a subarray in the timsort algorithm given the size of an initial array n. However I not understand how it works and why must minrun be a value 2^n (Which is to ensure optimality of merge())?

static int MIN_MERGE = 32;


public static int minRunLength(int n)
{   
    int r = 0;
    while (n >= MIN_MERGE)
    {
        r |= (n & 1);
        n >>= 1;
    }
    return n + r;
}

Any help would be much appreciated!

Upvotes: 1

Views: 218

Answers (0)

Related Questions