Insertion Sort

A simple O(n²) sorting algorithm that is surprisingly fast on small or nearly sorted arrays.

Context

Insertion sort is rarely taught as a “good” algorithm, yet it appears in real systems.

Why:

• it’s fast on nearly sorted data,
• it has tiny constant factors,
• it’s often used as a base case inside faster algorithms.

Core idea

• treat the prefix [0..i) as sorted
• take the element at i and store it once
• shift larger elements to the right to make space
• insert the stored value into the gap
• avoid swaps — assignments are cheaper and clearer

After each iteration, the sorted prefix grows by one.

Properties

• Time complexity
  • Worst / average: O(n²)
  • Best case (already sorted): O(n)
• Space complexity: O(1) (in-place)
• Stable: equal elements preserve order.
• Adaptive: performance improves as disorder decreases.

Implementation

class InsertionSort {
    void sort(int[] array) {
        for (var i = 1; i < array.length; i++) {
            var value = array[i];
            var previousIndex = i - 1;
            
            while (previousIndex >= 0 && array[previousIndex] > value) {
                array[previousIndex + 1] = array[previousIndex];
                previousIndex--;
            }
            
            array[previousIndex + 1] = value;
        }
    }
}