Insertion Sort

Key Points

• ›Best case O(n) on nearly sorted data — very practical
• ›Online algorithm: can sort elements as they arrive one by one
• ›Stable sort: equal elements retain their original order
• ›Used as the final pass in hybrid sorts like Timsort (Python, Java) for small subarrays
• ›Efficient for small inputs (n < 20) due to low overhead

Interactive Visualizer

Code Examples

func insertionSort(_ arr: inout [Int]) {
    let n = arr.count
    for i in 1..<n {
        let key = arr[i]
        var j = i - 1
        while j >= 0 && arr[j] > key {
            arr[j + 1] = arr[j]
            j -= 1
        }
        arr[j + 1] = key
    }
}

var nums = [12, 11, 13, 5, 6]
insertionSort(&nums)
print(nums)  // [5, 6, 11, 12, 13]

Practice Problems