Java 9 Data Structures and Algorithms

mergesort

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 ...