In the previous section, we tried to divide the array in such a way that when we sort each part, the entire array is sorted. We faced the problem that when we try to do that, the two parts are not equal in size causing the algorithm to sometimes take a quadratic amount of time. What if, instead of trying to divide the array in a way that sorting the parts would sort the whole, we just divide the array into two equal halves? Of course then, sorting the parts will not sort the entire array. However, if we have two array parts sorted on their own, can we merge them together to produce a sorted array as a whole? If we can do this efficiently enough, we would have an algorithm guaranteed to be efficient. As it turns out, it is possible. But we need to think about where the merged array will be stored. Since the values are being copied from the source array, the result needs to be stored in a separate place. So, we will need another storage of equal size for mergesort.

.

Merge of sorted...