Insertion Sort

Like bubble sort, insertion sort performs very well when the input is pre-sorted. However, it performs considerably better than bubble sort when the input is either randomly or reverse sorted. Although considerably better than bubble sort, it’s performance is still abysmal compared to quick and merge sort for large inputs.

History

Konrad Zuse created the insertion sort algorithm in 1945 in the first high level language: Plankalkül

Asymptotic Complexity

$O(n^2)$

Pseudo Code

sort:
    // side effect: rearranges the values in A
    A = input array

    for i = 0 to num of items in A:
        open_index = i
        temp = A[i]

        for j = i - 1 to 0:
            if temp > A[j]:
                shift A[j] to the right one position
                open_index += 1
            else:
                end inner loop
                
        A[open_index] = temp

Source Code

Full Repo

Relevant Files:

Click here for build and run instructions