# Insertion Sort

> For insertion sort, we used an ***incremental*** approach: having sorted the subarray A\[1 .. j - 1], we inserted the single element A\[j] into its proper place, yielding the sorted subarray A\[1 .. j].

Visualization: <https://www.hackerearth.com/practice/algorithms/sorting/insertion-sort/visualize/>

```cpp
INSERTION-SORT(A)
for j = 2 to A.length
    key = A[j]
    // Insert A[j] into the sorted sequence A[1 .. j - 1]
    i = j-1 
    while i > 0 and A[i] > key
        A[i+1] = A[i]
        i = i-1
    A[i+1] = key
```

* **Worst case:** $$O(n^2)$$, when it's reversed-order
* **Best case:** $$O(n)$$, when it's already sorted
