Insertion Sort in Python, Java and TypeScript

Insertion sort, printing its shifts on sorted, nearly sorted and reversed input.

Insertion sort is an outer loop that lifts each key and an inner loop that shifts larger items right until the key's place opens. The listings count comparisons and shifts on three inputs of seven items: sorted, nearly sorted with two neighbouring pairs exchanged, and reversed. Together they show the count tracking the disorder of the input rather than its size.

Insertion sort on sorted, nearly sorted and reversed input, in each language

insertion_sort_code.pypy

def insertion_sort(items: list[int]) -> tuple[int, int]:
    comparisons = shifts = 0
    for i in range(1, len(items)):
        key = items[i]
        j = i - 1
        while j >= 0:
            comparisons += 1
            if items[j] <= key:
                break
            items[j + 1] = items[j]
            shifts += 1
            j -= 1
        items[j + 1] = key
    return comparisons, shifts


for numbers in ([1, 2, 3, 4, 5, 6, 7], [2, 1, 3, 4, 6, 5, 7], [7, 6, 5, 4, 3, 2, 1]):
    before = " ".join(map(str, numbers))
    comparisons, shifts = insertion_sort(numbers)
    after = " ".join(map(str, numbers))
    print(f"{before} -> {after}: {comparisons} comparisons, {shifts} shifts")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

1 2 3 4 5 6 7 -> 1 2 3 4 5 6 7: 6 comparisons, 0 shifts
2 1 3 4 6 5 7 -> 1 2 3 4 5 6 7: 7 comparisons, 2 shifts
7 6 5 4 3 2 1 -> 1 2 3 4 5 6 7: 21 comparisons, 21 shifts

InsertionSortCode.javajava

import java.util.Arrays;
import java.util.stream.Collectors;

public class InsertionSortCode {
    record Counts(int comparisons, int shifts) {}

    static Counts insertionSort(int[] items) {
        int comparisons = 0;
        int shifts = 0;
        for (int i = 1; i < items.length; i++) {
            int key = items[i];
            int j = i - 1;
            while (j >= 0) {
                comparisons++;
                if (items[j] <= key) {
                    break;
                }
                items[j + 1] = items[j];
                shifts++;
                j--;
            }
            items[j + 1] = key;
        }
        return new Counts(comparisons, shifts);
    }

    static String joined(int[] items) {
        return Arrays.stream(items).mapToObj(String::valueOf).collect(Collectors.joining(" "));
    }

    public static void main(String[] args) {
        int[][] inputs = {{1, 2, 3, 4, 5, 6, 7}, {2, 1, 3, 4, 6, 5, 7}, {7, 6, 5, 4, 3, 2, 1}};
        for (int[] numbers : inputs) {
            String before = joined(numbers);
            Counts counts = insertionSort(numbers);
            System.out.println(before + " -> " + joined(numbers) + ": "
                    + counts.comparisons() + " comparisons, " + counts.shifts() + " shifts");
        }
    }
}

OutputRan with eclipse-temurin:25.0.4.1_1-jdk-noble (Java 25.0.4.1)

1 2 3 4 5 6 7 -> 1 2 3 4 5 6 7: 6 comparisons, 0 shifts
2 1 3 4 6 5 7 -> 1 2 3 4 5 6 7: 7 comparisons, 2 shifts
7 6 5 4 3 2 1 -> 1 2 3 4 5 6 7: 21 comparisons, 21 shifts

insertion_sort_code.tsts

interface Counts {
  comparisons: number;
  shifts: number;
}

function insertionSort(items: number[]): Counts {
  let comparisons = 0;
  let shifts = 0;
  for (let i = 1; i < items.length; i++) {
    const key = items[i];
    let j = i - 1;
    while (j >= 0) {
      comparisons++;
      if (items[j] <= key) {
        break;
      }
      items[j + 1] = items[j];
      shifts++;
      j--;
    }
    items[j + 1] = key;
  }
  return { comparisons, shifts };
}

const inputs: number[][] = [
  [1, 2, 3, 4, 5, 6, 7],
  [2, 1, 3, 4, 6, 5, 7],
  [7, 6, 5, 4, 3, 2, 1],
];
for (const numbers of inputs) {
  const before = numbers.join(" ");
  const { comparisons, shifts } = insertionSort(numbers);
  console.log(`${before} -> ${numbers.join(" ")}: ${comparisons} comparisons, ${shifts} shifts`);
}

OutputRan with node:24.22.0-trixie-slim (Node 24.22.0), TypeScript 5.9.3

1 2 3 4 5 6 7 -> 1 2 3 4 5 6 7: 6 comparisons, 0 shifts
2 1 3 4 6 5 7 -> 1 2 3 4 5 6 7: 7 comparisons, 2 shifts
7 6 5 4 3 2 1 -> 1 2 3 4 5 6 7: 21 comparisons, 21 shifts

All three printed the same three lines. Sorted input cost 6 comparisons and no shifts, one comparison per key. The nearly sorted input, 2 1 3 4 6 5 7, holds two inversions and cost two shifts and 7 comparisons: one per key, plus the shift of 2 when 1 is inserted, with no stopping comparison for 1 because it reaches the front. Reversed input cost 21 of each, every pair out of order.

The highlighted lines are the three steps of an insertion. The stopping test, items[j] <= key, ends the inner loop at the first item that is not larger than the key; writing < there would shift equal items too and make the sort unstable. The shift, items[j + 1] = items[j], copies an item one place right without touching the key, which is held in its own variable. The placing line, items[j + 1] = key, writes the key once, into the gap.

No standard library exposes insertion sort as a function, though the built-in sorts use it inside, on short runs. For one insertion into a list already sorted, Python has bisect.insort(items, x), which finds the place with a binary search in O(log n) and then shifts in O(n). Java gets the same from Collections.binarySearch, which returns the insertion point encoded as a negative number when the item is absent, followed by list.add(index, x). TypeScript has neither, so the inner loop above is the usual answer.

← → move through sections and cards