## Using divide-and-conquer instead

- Split array into subarray $A[1..n−1]$ and $A[n]$, recurse into $A[1..n−1]$ repeatedly
- Now we want to merge sorted subarray $A[1..n−1]$ and $A[n]$ by inserting $A[n]$ into the subarray. While we could use binary search to find the index (taking $O(gn)$), it takes $O(n)$ time to actually shift the elements. Therefore, merging takes $O(n)$.

Intuitively we are taking $O(n)$ time to sort one additional value in the array. If we have $n$ elements, then the total runtime is given by $O(n_{2})$, so runtime does not change.