Insertion Sort

Algorithms

Insertion sort is a simple sorting algorithm that builds the sorted array one element at a time by inserting each element into its correct position.

Algorithm

The algorithm works similar to how we sort playing cards in our hands: we pick an element and insert it into its correct position in the already sorted portion.

Time Complexity

Best case: $O (n)$ (when array is already sorted)
Average case: $O (n^{2})$
Worst case: $O (n^{2})$

Implementation

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # Move elements of arr[0..i-1] that are greater than key to one position ahead of their current position
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# Example usage with different numbers
arr = [45, 23, 78, 12, 56, 89, 34]
sorted_arr = insertion_sort(arr)
print("Sorted array:", sorted_arr)

Trace it by hand

ProblemRun insertion sort on a 5-element array

Insertion sort on [5, 2, 8, 1, 4]: write down the state of the array after each outer-loop pass (i.e., after each of the 4 insertions). Then count the total number of element shifts performed.