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.

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