Insertion Sort

Category: Sorting

The problem

For a small batch — a handful to a few dozen elements — pulling in a general-purpose, guaranteed-O(n log n) algorithm pays real setup cost (recursion, partitioning, auxiliary arrays) that dwarfs the actual work once n is small enough. What's needed at that scale is the algorithm with the lowest constant factor per comparison, not the best asymptotic ceiling — and real production sorts already make exactly that trade.

The solution

Grow a sorted prefix one element at a time: take the next element, and shift it left through the already-sorted prefix until it lands in its correct position. The cost of that shift is proportional to how many prefix elements are actually out of place relative to it — which means the total cost tracks the array's total number of inversions, not just its size. An already-sorted array has zero inversions (every element shifts zero positions, O(n) total); a reverse-sorted array has the maximum possible number (every element shifts all the way to the front, O(n²) total). This is exactly why the JDK's own Arrays.sort/TimSort switch to insertion sort below a small size threshold instead of paying merge/quicksort's setup cost on a tiny run.

flowchart TB
    subgraph "sorted prefix [1,3,5], next = 2"
        direction LR
        P0["1"] --- P1["3"] --- P2["5"] --- N["2 →"]
    end
    subgraph "2 shifted left past 5 and 3, inserted after 1"
        direction LR
        Q0["1"] --- Q1["2"] --- Q2["3"] --- Q3["5"]
    end

Classic example

classic/InsertionSort is generic over Comparator<? super T> — no Arrays.sort/Collections.sort shortcut — the shift loop moves elements one slot at a time using plain assignment, no swaps. InsertionSortTest covers an unordered array, an already-sorted array, a reverse-sorted array, duplicates, a single-element and an empty array, a custom (descending) comparator, and both null-argument guards.

Applied example: telecom call-detail-record batch sort

applied/CallDetailRecordSort sorts a small batch of call detail records by start time before handing them to a real-time rating/billing engine. A single subscriber's calls within a short billing window is exactly the shape this algorithm is good at: a small n, and — since carrier-side event ingestion is itself roughly chronological — usually already close to sorted by the time it reaches this stage. The class documents RECOMMENDED_MAX_BATCH_SIZE (64) as the same kind of size threshold real production sorts use before switching away from insertion sort. CallDetailRecordSortTest covers records sorted into the correct order, that the input array is left untouched (the method returns a new sorted array), and the null-argument guard.

Benchmark

./gradlew :sorting:insertion-sort:jmh

Real run on this machine (JMH 1.37, JDK 26.0.2, 2 warmup + 3 measurement iterations, 1 fork). Same three orderings and sizes as this repo's Bubble Sort benchmark, so the two are directly comparable:

At size=10,000, random is ~2,384x slower than already-sorted — the inversion-count claim from "The solution" above, made measurable. Worth comparing directly against this repo's Bubble Sort benchmark: same orderings, same sizes, same machine — insertion sort's random-case cost at size=10,000 (73,063.752 µs) is well under half of bubble sort's (337,009.203 µs), which matches the well-known result that insertion sort does roughly half the element moves bubble sort does for the same disorder, even though both are O(n²) in the worst case. Same asymptotic class, measurably different constant.

When not to use it

• Need a guaranteed O(n log n) bound for a large or genuinely unordered dataset? Use Merge Sort or Quick Sort from this repo — the benchmark above shows exactly how badly O(n²) degrades once n stops being small.
• This module's real value is specifically small-n or already-nearly-sorted batches — that's a narrow, real niche (which is why it's the one classic O(n²) sort that still ships inside production sort implementations today), not a general-purpose choice.

Test coverage

100% instruction coverage, 100% branch coverage (JaCoCo). Reproduce it yourself:

./gradlew :sorting:insertion-sort:jacocoTestReport

Report at sorting/insertion-sort/build/reports/jacoco/test/html/index.html.

Further reading

• Cormen, Leiserson, Rivest & Stein — Introduction to Algorithms (CLRS), 3rd/4th ed., Chapter 2, "Getting Started" — insertion sort is CLRS's own opening algorithm, used to introduce loop invariants and asymptotic analysis.
• Sedgewick & Wayne — Algorithms, 4th ed., section 2.1, "Elementary Sorts" — includes the same real-world detail this module leans on: production sorts fall back to insertion sort for small subarrays.

Unit tests

package com.algorithms.sorting.insertionsort.classic;

import org.junit.jupiter.api.Test;

import java.util.Comparator;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class InsertionSortTest {

    @Test
    void sortsAnUnorderedArrayIntoAscendingOrder() {
        Integer[] array = {5, 3, 8, 1, 9, 2};

        InsertionSort.sort(array, Comparator.naturalOrder());

        assertThat(array).containsExactly(1, 2, 3, 5, 8, 9);
    }

    @Test
    void alreadySortedArrayStaysSorted() {
        Integer[] array = {1, 2, 3, 4, 5};

        InsertionSort.sort(array, Comparator.naturalOrder());

        assertThat(array).containsExactly(1, 2, 3, 4, 5);
    }

    @Test
    void reverseSortedArrayEndsUpAscending() {
        Integer[] array = {5, 4, 3, 2, 1};

        InsertionSort.sort(array, Comparator.naturalOrder());

        assertThat(array).containsExactly(1, 2, 3, 4, 5);
    }

    @Test
    void duplicatesAreHandledCorrectly() {
        Integer[] array = {3, 1, 3, 2, 1};

        InsertionSort.sort(array, Comparator.naturalOrder());

        assertThat(array).containsExactly(1, 1, 2, 3, 3);
    }

    @Test
    void singleElementArrayStaysUnchanged() {
        Integer[] array = {42};

        InsertionSort.sort(array, Comparator.naturalOrder());

        assertThat(array).containsExactly(42);
    }

    @Test
    void emptyArrayStaysEmpty() {
        Integer[] array = {};

        InsertionSort.sort(array, Comparator.naturalOrder());

        assertThat(array).isEmpty();
    }

    @Test
    void sortsUsingACustomComparatorForDescendingOrder() {
        Integer[] array = {1, 5, 3, 2, 4};

        InsertionSort.sort(array, Comparator.reverseOrder());

        assertThat(array).containsExactly(5, 4, 3, 2, 1);
    }

    @Test
    void rejectsANullArray() {
        assertThatThrownBy(() -> InsertionSort.sort(null, Comparator.naturalOrder()))
                .isInstanceOf(IllegalArgumentException.class);
    }

    @Test
    void rejectsANullComparator() {
        assertThatThrownBy(() -> InsertionSort.sort(new Integer[] {1, 2}, null))
                .isInstanceOf(IllegalArgumentException.class);
    }
}

package com.algorithms.sorting.insertionsort.applied;

import org.junit.jupiter.api.Test;

import java.time.Instant;
import java.time.temporal.ChronoUnit;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class CallDetailRecordSortTest {

    private static final Instant BASE = Instant.parse("2026-08-17T09:00:00Z");

    @Test
    void sortByStartTimeOrdersRecordsAscendingByStartTime() {
        CallDetailRecordSort sorter = new CallDetailRecordSort();
        CallDetailRecord[] records = {
                record("c", 5),
                record("a", 1),
                record("b", 3),
        };

        CallDetailRecord[] sorted = sorter.sortByStartTime(records);

        assertThat(sorted).extracting(CallDetailRecord::callId).containsExactly("a", "b", "c");
    }

    @Test
    void sortByStartTimeDoesNotMutateTheInputArray() {
        CallDetailRecordSort sorter = new CallDetailRecordSort();
        CallDetailRecord[] records = {record("b", 2), record("a", 1)};

        sorter.sortByStartTime(records);

        assertThat(records).extracting(CallDetailRecord::callId).containsExactly("b", "a");
    }

    @Test
    void rejectsNullRecords() {
        CallDetailRecordSort sorter = new CallDetailRecordSort();

        assertThatThrownBy(() -> sorter.sortByStartTime(null)).isInstanceOf(IllegalArgumentException.class);
    }

    private static CallDetailRecord record(String callId, long offsetMinutes) {
        return new CallDetailRecord(callId, BASE.plus(offsetMinutes, ChronoUnit.MINUTES));
    }
}

View full JaCoCo coverage report →