Incomplete Implementation

Merge sort is a sorting algorithm. It works by splitting an array in half, sorting both halves recursively and then merging those halves together to sort the entire array. Your friend is working on an implementation of the merge sort algorithm, but unfortunately he is not quite there yet: he can only sort half of the array ! In great despair he turns to you for help: can you use his unfinished code to write an algorithm that sorts an array completely?

In its current state, your friend’s code is a sorting function that can be run on arbitrary subarrays, as long as it is precisely half as long as the original array . It then correctly sorts this subarray. Note that a subarray does not have to be contiguous, it can be any subset of the original array!

You decide to play around with this function. You start with a jumbled array and try to sort it (see the image above). After choosing several subarrays and using them as input for the sorting function, you end up with a sorted array. Interestingly, it seems that no matter what the original array is, you can always sort it completely by invoking your friend’s sorting function several times. You decide that this makes for a good challenge: you want to extend the code to work for a full array, making least number of calls to the sorting function.

Given an arbitrary array with length $n$ divisible by $4$ , consisting of $1$ to $n$ , what is the least number of calls to the sorting function that will guarantee the array will be completely sorted?