Insertion sort

Using divide-and-conquer instead

1. Split array into subarray $A[\mathrm{1..}n-1]$ and $A[n]$, recurse into $A[\mathrm{1..}n-1]$ repeatedly
2. Now we want to merge sorted subarray $A[\mathrm{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(\log n)$), 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.