We want to develop an algorithm that sorts an array of elements efficiently. Our strategy will be simple; we will somehow try to divide the array into two halves in such a way that sorting each half will complete the sorting. If we can achieve this, we can recursively call the sorting algorithm this way. We already know that the number of levels of recursive call will be of the order of lg n where lg m is the logarithm of m with the base 2. So, if we can manage to cut the array in a time in the order of n, we will still have a complexity of O(n lg n) This is much better than O(n 2 ), which we saw in the previous chapter. But how do we cut the array that way? Let's try to cut the following array as follows:
10, 5, 2, 3, 78, 53, 3,1,1,24,1,35,35,2,67,4,33,30
If we trivially cut this array, each part will contain all sorts of values. Sorting these individual parts would then not cause the entire array to be sorted. Instead, we have to cut the array in such a way that all the elements...