Notes by Lex Toumbourou

Insertion Sort is one of the most widely known sorting Algorithm. The algorithm iteratively compares each element with its left neighbours, shifting them one position to the right if they are greater. It has an average and worst-case run time of $O(n^2)$, so it is one of the slowest algorithms for large input sizes; however, if the list is mostly sorted, it can be one of the best-performing options.

Image via Wikimedia commons.

Python code

def insertion_sort(v):
    j = 1

    for i in range(j, len(v)):
        key = v[j]
        i = j - 1
        while i >= 0 and v[i] > key:
            v[i + 1] = v[i]
            i = i - 1
        v[i + 1] = key
        j = j + 1

    return v

Time Complexity

• Worst case run-time: $O(n^2)$
• Avg run-time: $O(n^2)$
• Best case run-time: $O(n)$ (when the array is already sorted)

Space Complexity

• $O(1)$ (in-place sorting algorithm)