Topics › Sorting › Sorting-I

Insertion Sorting

Easy TUF ID 944 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an array arr of n integers. Sort it in non-decreasing order using the insertion sort algorithm: take the elements one at a time and insert each into its correct position among the elements already processed, the way most people sort a hand of playing cards.

Constraints: 1 ≤ n ≤ 10^3, values fit in a 32-bit signed integer. Duplicates and negative numbers are allowed.

Example 1

arr = [14, 9, 15, 12, 6, 8, 13]
answer = [6, 8, 9, 12, 13, 14, 15]    // every element is <= the one after it

Example 2

arr = [5, 4, 4, 1, 1]
answer = [1, 1, 4, 4, 5]              // duplicates stay together

Approach 1: Insert by swapping leftwards

Intuition. Keep the invariant arr[0..i-1] is sorted. It holds trivially for i = 1 (one element). To extend it by one, take arr[i] and walk it to the left: while the element on its left is larger, swap the two. Each swap moves the new element one step closer to its place and keeps everything else in order. When the walk stops, either we reached the front or the left neighbour is <= the element, so the prefix arr[0..i] is sorted. Do this for i = 1, 2, ..., n - 1 and the whole array is sorted.

This is the version in the A2Z sheet. It is a chain of adjacent swaps, so each step is three assignments.

Algorithm.

1. For i from 1 to n - 1:
2. Set j = i.
3. While j > 0 and arr[j - 1] > arr[j]: swap arr[j - 1] and arr[j], then j--.

static void insertionSortSwaps(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int j = i;
        while (j > 0 && arr[j - 1] > arr[j]) {
            int tmp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = tmp;
            j--;
        }
    }
}

Complexity. Time O(n^2) in the worst case (reversed input: element i travels i steps, n(n-1)/2 swaps in total) and O(n) in the best case (sorted input: one comparison per element, no swaps). Space O(1).

More precisely the running time is O(n + I) where I is the number of inversions, pairs (p, q) with p < q and arr[p] > arr[q]. Every swap removes exactly one inversion, and the comparisons are at most one more than the swaps per element. That is why insertion sort is the algorithm of choice for data that is almost sorted: few inversions, near-linear time.

Approach 2: Insert by shifting

Intuition. In approach 1 the element being inserted is written back into the array at every step, only to be moved again on the next step. We can hold it in a variable (key), shift the larger elements one slot to the right, and write key exactly once when the hole reaches the right place. Same comparisons, roughly a third of the writes. This is the classic textbook formulation.

Algorithm.

1. For i from 1 to n - 1: let key = arr[i] and j = i - 1.
2. While j >= 0 and arr[j] > key: arr[j + 1] = arr[j], j--.
3. Write arr[j + 1] = key.

static void insertionSortShift(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Dry run on arr = [14, 9, 15, 12, 6, 8, 13]:

The sorted prefix grows by one each row; the elements to the right of i are untouched until their turn comes.

Complexity. Time O(n^2) worst, O(n) best, O(n + I) in general, exactly as approach 1. Space O(1).

Note the loop condition j >= 0 && arr[j] > key: the j >= 0 must come first so that arr[-1] is never evaluated. When the loop exits, j + 1 is the first index whose element is <= key (or 0), which is precisely where key belongs.

Approach 3: Binary search for the insertion point

Intuition. The prefix arr[0..i-1] is sorted, so we do not need a linear scan to find where key goes: a binary search finds the position in O(log i) comparisons. We look for the first index lo in [0, i] with arr[lo] > key (the upper bound), shift arr[lo..i-1] right by one, and place key at lo. Choosing the position after all elements equal to key keeps the sort stable.

The number of moves does not change, so the overall worst case is still quadratic. What improves is the comparison count, which matters when comparisons are expensive (long strings, composite keys, remote lookups) or when you want the fewest comparisons for small arrays.

Algorithm.

1. For i from 1 to n - 1: let key = arr[i], lo = 0, hi = i.
2. While lo < hi: mid = (lo + hi) / 2; if arr[mid] <= key set lo = mid + 1, else hi = mid.
3. Shift arr[lo..i-1] one position right, then set arr[lo] = key.

static void insertionSortBinary(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int lo = 0, hi = i;                   // insertion index lies in [lo, hi]
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (arr[mid] <= key) lo = mid + 1; else hi = mid;
        }
        for (int j = i; j > lo; j--) arr[j] = arr[j - 1];
        arr[lo] = key;
    }
}

Complexity. Time: O(n log n) comparisons, but still O(n^2) element moves in the worst case, so O(n^2) overall; O(n log n) when the input is already sorted (no moves, but the binary search still runs). Space O(1).

The >>> 1 instead of / 2 avoids overflow in lo + hi; irrelevant for n ≤ 10^3, but it is the habit that keeps binary search correct at scale. When lo == i after the search, the shift loop does nothing and arr[i] = key rewrites the value that was already there.

Edge cases and pitfalls

• Empty or single-element array. The outer loop starts at i = 1 and 1 < n is false, so nothing runs. Correct, no special case needed.
• Order of the && operands. j > 0 && arr[j - 1] > arr[j] and j >= 0 && arr[j] > key rely on short-circuit evaluation. Swap the operands and you read arr[-1].
• Strict > gives stability. Shifting stops at the first element that is <= key, so an equal element already in the prefix stays to the left of the new one. Using >= in the while condition (or < in the binary search) sorts correctly but breaks stability.
• Compare values directly. arr[j] - key > 0 overflows near the int limits; the tests include Integer.MIN_VALUE and Integer.MAX_VALUE in one array.
• Writing key at j instead of j + 1. After the shifting loop, j points at the element that is <= key (or is -1); the hole is one to the right. This is the most common bug in approach 2.
• Already sorted input is the best case, reversed input the worst. For [1, 2, 3, 4, 5] approach 1 and 2 do n - 1 comparisons and no moves. For [5, 4, 3, 2, 1] every insertion walks to the front.
• Where insertion sort is actually used. Library sorts (including Java’s dual-pivot quicksort and TimSort) switch to insertion sort for small ranges, because its constant factor beats merge or quick sort below a few dozen elements.

Related problems

• Recursive Insertion Sort is the same algorithm with the outer loop written as recursion.
• Selection Sort and Bubble Sort are the other two elementary quadratic sorts; comparing their best and worst cases with insertion sort is a classic exam question.
• Merge Sorting counts the same inversions that bound insertion sort’s running time, but removes them in O(n log n).