Using divide-and-conquer instead

  1. Split array into subarray and , recurse into repeatedly
  2. Now we want to merge sorted subarray and by inserting into the subarray. While we could use binary search to find the index (taking ), it takes time to actually shift the elements. Therefore, merging takes .

Intuitively we are taking time to sort one additional value in the array. If we have elements, then the total runtime is given by , so runtime does not change.