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/

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