Insertion Sort
O(n²)

History

Insertion Sort is one of the simplest sorting algorithms. It was developed based on how people typically sort playing cards in their hands. The algorithm was first described by John Mauchly in 1946, making it one of the earliest sorting algorithms to be formally analyzed. Despite its O(n²) average complexity, it remains widely used due to its simplicity, low overhead, and excellent performance on small or nearly sorted datasets.

How it works

Start from the second element (index 1)
Compare it with elements before it
Shift larger elements one position ahead
Insert the element at the correct position
Repeat for all remaining elements

When to use

Small datasets: Overhead is minimal for n < 50
Nearly sorted data: Approaches O(n) performance
Online sorting: Can sort data as it arrives
As a subroutine: Used in hybrid algorithms like Timsort

Implementation

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

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

func insertionSort(arr []int) []int {
    for i := 1; i < len(arr); i++ {
        key := arr[i]
        j := i - 1
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1] = key
    }
    return arr
}

fn insertion_sort<T: Ord>(arr: &mut [T]) {
    for i in 1..arr.len() {
        let mut j = i;
        while j > 0 && arr[j - 1] > arr[j] {
            arr.swap(j - 1, j);
            j -= 1;
        }
    }
}