Insertion sort

In plain words

You hold some playing cards in your left hand, in order. You take one new card with your right hand. You move it from the right to the left past each card that is larger. Then you put it in the gap. Now the cards in your left hand are in order again, and they are one more. You do this for each new card.

Insertion sort does this on an array. The left part of the array is sorted. The algorithm takes the first item to the right of this part, and inserts it at the correct place in the left part.

See it run

INSERTION-SORT(A)
1for i ← 1 to n − 1 do
2key ← A[i]
3j ← i − 1
4while j ≥ 0 and A[j] > key do ▷ > and not ≥ keeps the sort stable
5A[j + 1] ← A[j]
6j ← j − 1
7A[j + 1] ← key

0 / 0 Speed Input

Use your own input

Type the input as JSON, in the same form as a preset.

Open the full player

The problem

The input is an array $A[0 \ldots n-1]$ of items with a total order. The output is the same array, with its items in non-decreasing order. This is the sorting problem. The algorithm changes the array in place.

The algorithm

INSERTION-SORT(A)
1for i ← 1 to n − 1 do
2key ← A[i]
3j ← i − 1
4while j ≥ 0 and A[j] > key do ▷ > and not ≥ keeps the sort stable
5A[j + 1] ← A[j]
6j ← j − 1
7A[j + 1] ← key

Line L2 takes the next item and keeps it in $key$ . Lines L4 to L6 move each larger item of the sorted part one place to the right. This opens a gap. Line L7 puts $key$ in the gap.

Example

Sort $A = [5, 2, 4, 6, 1, 3]$ . The bar shows the end of the sorted part.

i	key	the array after the step
start		5 \| 2 4 6 1 3
1	2	2 5 \| 4 6 1 3
2	4	2 4 5 \| 6 1 3
3	6	2 4 5 6 \| 1 3
4	1	1 2 4 5 6 \| 3
5	3	1 2 3 4 5 6 \|

In step 4, the key 1 moves past four items. In step 3, the key 6 moves past no item.

Correctness

The proof uses a loop invariant for the loop of line L1:

Before the step for $i$ , the part $A[0 \ldots i-1]$ holds the items that were at the start in $A[0 \ldots i-1]$ , in non-decreasing order.

At the start $i = 1$ , and a part with one item is sorted. The inner loop moves the items of the sorted part that are larger than $key$ one place right, and line L7 puts $key$ after the items that are not larger. So after the step, $A[0 \ldots i]$ is sorted. When the loop stops, $i = n$ , and the full array is sorted. The full proof is below.

Proof: Insertion sort sorts the array and keeps its itemsfull

Let $A_0$ be the array at the start. We prove the invariant of the outer loop:

(I) Before the step for $i$ , the part $A[0 \ldots i-1]$ is a permutation of $A_0[0 \ldots i-1]$ in non-decreasing order, and $A[i \ldots n-1] = A_0[i \ldots n-1]$ .

Start. For $i = 1$ , the part $A[0 \ldots 0]$ has one item, so it is sorted. No item has moved yet.

Step. Assume (I) before the step for $i$ . Line L2 sets $key = A[i] = A_0[i]$ . For the inner loop we use this invariant:

(J) $-1 \le j \le i-1$ . The part $A[0 \ldots j]$ is not changed. The part $A[j+2 \ldots i]$ is the old $A[j+1 \ldots i-1]$ , moved one place right. Each item of $A[j+2 \ldots i]$ is larger than $key$ .

Before the first test of line L4, $j = i - 1$ and $A[j+2 \ldots i]$ is empty, so (J) is true. If the test of line L4 is true, then $A[j] > key$ . Line L5 copies $A[j]$ to $A[j+1]$ , and line L6 makes $j$ one less. So (J) is true again. The value $j$ becomes smaller in each step and $j \ge -1$ , so the inner loop stops.

When the inner loop stops, $j = -1$ or $A[j] \le key$ . Line L7 puts $key$ at $A[j+1]$ . Now:

each item of $A[0 \ldots j]$ is at most $key$ , because the old part was sorted and $A[j] \le key$ , or the part is empty;
$A[j+1] = key$ ;
each item of $A[j+2 \ldots i]$ is larger than $key$ , by (J), and these items are in the old order.

So $A[0 \ldots i]$ is sorted. It holds the old $A[0 \ldots i-1]$ and $A_0[i]$ , so it is a permutation of $A_0[0 \ldots i]$ . The items after $i$ did not change. This is (I) for $i + 1$ .

End. The loop stops with $i = n$ . By (I), $A[0 \ldots n-1]$ is a permutation of $A_0$ in non-decreasing order. $\blacksquare$

Stability. An item moves right in line L5 only past an item that is larger than $key$ . So $key$ never moves before an item that is equal to it and that was before it in $A_0$ .

All proofs on one page

Complexity

The inner loop runs once for each pair of indices $j < i$ with $A[j] > A[i]$ . Such a pair is an inversion. Let $d$ be the number of inversions of the input. Then the time is $\Theta(n + d)$ .

The worst case is an array in decreasing order. It has $d = n(n-1)/2$ inversions, so the time is $\Theta(n^2)$ . The algorithm does $n(n-1)/2$ comparisons and $n(n-1)/2$ moves.
The best case is an array that is already sorted. It has $d = 0$ , so the time is $\Theta(n)$ , with $n - 1$ comparisons.
On a random permutation, the expected number of inversions is $n(n-1)/4$ , so the average time is $\Theta(n^2)$ .
The extra space is $\Theta(1)$ : the key and two indices.

Properties

Stable. Line L4 stops at an item equal to $key$ , so equal items keep their order.
In place. The extra space is a fixed number of variables.
Adaptive. An input with few inversions sorts fast.
Online. The algorithm can sort the items while they arrive, because each step needs only the items before it.

Variants and improvements

Binary insertion sort. Use binary search to find the place of $key$ . This makes the number of comparisons $O(n \log n)$ , but the number of moves stays $\Theta(n^2)$ in the worst case.
Shell sort. Do insertion sort on items that are far apart first, with a decreasing sequence of gaps. Good gap sequences make the time much less than $\Theta(n^2)$ .
A sentinel. Put the smallest item at $A[0]$ first. Then the test $j \ge 0$ in line L4 is not necessary.

When to use it

Use insertion sort for small arrays, of about 10 to 30 items. For such sizes it is often faster than merge sort and quicksort, because its loop is simple. Many library sorts, such as introsort and Timsort, switch to insertion sort for small parts. Also use it when the input is almost sorted.

Do not use it for large arrays in random order. The time grows as $n^2$ .

Pitfalls

Comparing with ≥. The test $A[j] \ge key$ in line L4 also gives a sorted array, but the sort is not stable.
Swapping instead of shifting. A swap in each step of the inner loop does three writes. A shift does one.
The index $j$ becomes $-1$ . In a language with unsigned indices, $j - 1$ can wrap around. Test $j > 0$ and use $A[j-1]$ , or use a signed type.

Implementations

Each implementation follows the pseudocode above. A comment @line links a line of code to a line of the pseudocode. Point at a line of the pseudocode to see the matching code. The build runs the native tests of each language.

insertion_sort.pytests passPage Raw GitHub

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.

from typing import Protocol, TypeVar


class Ordered(Protocol):
    def __lt__(self, other: "Ordered", /) -> bool: ...


T = TypeVar("T", bound=Ordered)


def insertion_sort(a: list[T]) -> None:
    """Sort the list a in place, in non-decreasing order. The sort is stable."""
    for i in range(1, len(a)):  # @line L1
        key = a[i]  # @line L2
        j = i - 1  # @line L3
        while j >= 0 and key < a[j]:  # @line L4
            a[j + 1] = a[j]  # @line L5
            j -= 1  # @line L6
        a[j + 1] = key  # @line L7

test_insertion_sort.py 43 lines

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.

import random

from insertion_sort import insertion_sort


def test_example() -> None:
    a = [5, 2, 4, 6, 1, 3]
    insertion_sort(a)
    assert a == [1, 2, 3, 4, 5, 6]


def test_edges() -> None:
    for a in ([], [1], [2, 1], [1, 1, 1], [3, 2, 1]):
        b = list(a)
        insertion_sort(b)
        assert b == sorted(a)


def test_stable() -> None:
    a = [(2, "a"), (1, "b"), (2, "c"), (1, "d")]

    class Key:
        def __init__(self, p: tuple[int, str]) -> None:
            self.p = p

        def __lt__(self, other: "Key") -> bool:
            return self.p[0] < other.p[0]

    b = [Key(p) for p in a]
    insertion_sort(b)
    assert [k.p for k in b] == [(1, "b"), (1, "d"), (2, "a"), (2, "c")]


def test_random_against_sorted() -> None:
    rng = random.Random(2150)
    for _ in range(500):
        a = [rng.randint(-50, 50) for _ in range(rng.randint(0, 40))]
        b = list(a)
        insertion_sort(b)
        assert b == sorted(a)

insertion_sort.hpptests passPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.

#pragma once

#include <cstddef>
#include <span>
#include <utility>

namespace algo {

// insertion_sort sorts a in place, in non-decreasing order. The sort is stable.
template <typename T>
void insertion_sort(std::span<T> a) {
    for (std::size_t i = 1; i < a.size(); i++) {   // @line L1
        T key = std::move(a[i]);                    // @line L2
        std::size_t j = i;                          // @line L3: j is one more than in the pseudocode
        while (j > 0 && key < a[j - 1]) {           // @line L4
            a[j] = std::move(a[j - 1]);             // @line L5
            j--;                                    // @line L6
        }
        a[j] = std::move(key);                      // @line L7
    }
}

}  // namespace algo

test_insertion_sort.cpp 32 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.

#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <string>
#include <vector>

#include "insertion_sort.hpp"

int main() {
    std::vector<int> a{5, 2, 4, 6, 1, 3};
    algo::insertion_sort(std::span<int>(a));
    assert((a == std::vector<int>{1, 2, 3, 4, 5, 6}));

    std::vector<std::string> w{"pear", "fig", "apple"};
    algo::insertion_sort(std::span<std::string>(w));
    assert((w == std::vector<std::string>{"apple", "fig", "pear"}));

    std::mt19937 rng(2150);
    for (int t = 0; t < 500; t++) {
        std::vector<int> b(rng() % 41);
        for (auto& v : b) v = static_cast<int>(rng() % 101) - 50;
        auto want = b;
        algo::insertion_sort(std::span<int>(b));
        std::ranges::sort(want);
        assert(b == want);
    }
    std::cout << "ok\n";
}

InsertionSort.javaPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.

/** Insertion sort. */
public final class InsertionSort {
    private InsertionSort() {}

    /** Sorts a in place, in non-decreasing order. */
    public static void sort(long[] a) {
        for (int i = 1; i < a.length; i++) {      // @line L1
            long key = a[i];                      // @line L2
            int j = i - 1;                        // @line L3
            while (j >= 0 && a[j] > key) {        // @line L4
                a[j + 1] = a[j];                  // @line L5
                j--;                              // @line L6
            }
            a[j + 1] = key;                       // @line L7
        }
    }

    /** Sorts a in place by the natural order of its items. The sort is stable. */
    public static <T extends Comparable<? super T>> void sort(T[] a) {
        for (int i = 1; i < a.length; i++) {
            T key = a[i];
            int j = i - 1;
            while (j >= 0 && a[j].compareTo(key) > 0) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = key;
        }
    }
}

InsertionSortTest.java 40 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.

import static org.junit.jupiter.api.Assertions.assertArrayEquals;

import java.util.Arrays;
import java.util.Random;
import org.junit.jupiter.api.Test;

class InsertionSortTest {
    @Test
    void example() {
        long[] a = {5, 2, 4, 6, 1, 3};
        InsertionSort.sort(a);
        assertArrayEquals(new long[] {1, 2, 3, 4, 5, 6}, a);
    }

    @Test
    void edges() {
        long[] e = {};
        InsertionSort.sort(e);
        assertArrayEquals(new long[] {}, e);
        String[] w = {"pear", "fig", "apple"};
        InsertionSort.sort(w);
        assertArrayEquals(new String[] {"apple", "fig", "pear"}, w);
    }

    @Test
    void randomAgainstArraysSort() {
        Random rng = new Random(2150);
        for (int t = 0; t < 500; t++) {
            long[] a = new long[rng.nextInt(41)];
            for (int i = 0; i < a.length; i++) a[i] = rng.nextInt(101) - 50;
            long[] want = a.clone();
            Arrays.sort(want);
            InsertionSort.sort(a);
            assertArrayEquals(want, a);
        }
    }
}

insertion_sort.ctests passPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.

#include "insertion_sort.h"

void insertion_sort(int64_t *a, size_t n) {
    for (size_t i = 1; i < n; i++) {         // @line L1
        int64_t key = a[i];                  // @line L2
        size_t j = i;                        // @line L3: j is one more than in the pseudocode, so it stays unsigned
        while (j > 0 && a[j - 1] > key) {    // @line L4
            a[j] = a[j - 1];                 // @line L5
            j--;                             // @line L6
        }
        a[j] = key;                          // @line L7
    }
}

insertion_sort.h 13 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.

#ifndef INSERTION_SORT_H
#define INSERTION_SORT_H

#include <stddef.h>
#include <stdint.h>

// insertion_sort sorts a[0..n-1] in place, in non-decreasing order. The sort is stable.
void insertion_sort(int64_t *a, size_t n);

#endif

test_insertion_sort.c 34 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "insertion_sort.h"

static int cmp(const void *p, const void *q) {
    int64_t a = *(const int64_t *)p, b = *(const int64_t *)q;
    return (a > b) - (a < b);
}

int main(void) {
    int64_t a[] = {5, 2, 4, 6, 1, 3};
    const int64_t want[] = {1, 2, 3, 4, 5, 6};
    insertion_sort(a, 6);
    assert(memcmp(a, want, sizeof a) == 0);
    insertion_sort(NULL, 0);

    srand(2150);
    int64_t b[40], c[40];
    for (int t = 0; t < 500; t++) {
        size_t n = (size_t)(rand() % 41);
        for (size_t i = 0; i < n; i++) b[i] = c[i] = rand() % 101 - 50;
        insertion_sort(b, n);
        qsort(c, n, sizeof c[0], cmp);
        assert(n == 0 || memcmp(b, c, n * sizeof b[0]) == 0);
    }
    puts("ok");
    return 0;
}

InsertionSort.csPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.

namespace Algorithm;

/// <summary>Insertion sort.</summary>
public static class InsertionSort
{
    /// <summary>Sorts a in place, in non-decreasing order. The sort is stable.</summary>
    public static void Sort<T>(Span<T> a) where T : IComparable<T>
    {
        for (int i = 1; i < a.Length; i++)                  // @line L1
        {
            T key = a[i];                                   // @line L2
            int j = i - 1;                                  // @line L3
            while (j >= 0 && a[j].CompareTo(key) > 0)       // @line L4
            {
                a[j + 1] = a[j];                            // @line L5
                j--;                                        // @line L6
            }
            a[j + 1] = key;                                 // @line L7
        }
    }
}

InsertionSortTests.cs 42 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.

using Algorithm;
using Xunit;

public class InsertionSortTests
{
    [Fact]
    public void Example()
    {
        long[] a = [5, 2, 4, 6, 1, 3];
        InsertionSort.Sort<long>(a);
        Assert.Equal(new long[] { 1, 2, 3, 4, 5, 6 }, a);
    }

    [Fact]
    public void Edges()
    {
        long[] e = [];
        InsertionSort.Sort<long>(e);
        Assert.Empty(e);
        string[] w = ["pear", "fig", "apple"];
        InsertionSort.Sort<string>(w);
        Assert.Equal(new[] { "apple", "fig", "pear" }, w);
    }

    [Fact]
    public void RandomAgainstArraySort()
    {
        var rng = new Random(2150);
        for (int t = 0; t < 500; t++)
        {
            var a = new long[rng.Next(41)];
            for (int i = 0; i < a.Length; i++) a[i] = rng.Next(101) - 50;
            var want = (long[])a.Clone();
            Array.Sort(want);
            InsertionSort.Sort<long>(a);
            Assert.Equal(want, a);
        }
    }
}

insertionSort.jstests passPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.

/**
 * Sorts a in place, in non-decreasing order, and returns it. The sort is stable.
 * @template T
 * @param {T[]} a
 * @returns {T[]}
 */
export function insertionSort(a) {
  for (let i = 1; i < a.length; i++) { // @line L1
    const key = a[i]; // @line L2
    let j = i - 1; // @line L3
    while (j >= 0 && a[j] > key) { // @line L4
      a[j + 1] = a[j]; // @line L5
      j--; // @line L6
    }
    a[j + 1] = key; // @line L7
  }
  return a;
}

insertionSort.test.js 30 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.

import { test } from "node:test";
import assert from "node:assert/strict";
import { insertionSort } from "./insertionSort.js";

test("example", () => {
  assert.deepEqual(insertionSort([5, 2, 4, 6, 1, 3]), [1, 2, 3, 4, 5, 6]);
});

test("edges", () => {
  assert.deepEqual(insertionSort([]), []);
  assert.deepEqual(insertionSort([1]), [1]);
  assert.deepEqual(insertionSort([3, 2, 1, 1]), [1, 1, 2, 3]);
  assert.deepEqual(insertionSort(["pear", "fig", "apple"]), ["apple", "fig", "pear"]);
});

test("random against Array.prototype.sort", () => {
  let s = 2150;
  const next = (m) => {
    s = (Math.imul(s, 1103515245) + 12345) >>> 0;
    return (s >>> 8) % m;
  };
  for (let t = 0; t < 500; t++) {
    const a = Array.from({ length: next(41) }, () => next(101) - 50);
    const want = [...a].sort((p, q) => p - q);
    assert.deepEqual(insertionSort([...a]), want);
  }
});

insertionSort.tstests passPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.

/** Sorts a in place, in non-decreasing order, and returns it. The sort is stable. */
export function insertionSort<T extends number | string>(a: T[]): T[] {
  for (let i = 1; i < a.length; i++) { // @line L1
    const key = a[i]; // @line L2
    let j = i - 1; // @line L3
    while (j >= 0 && a[j] > key) { // @line L4
      a[j + 1] = a[j]; // @line L5
      j--; // @line L6
    }
    a[j + 1] = key; // @line L7
  }
  return a;
}

insertionSort.test.ts 30 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.

import { test } from "node:test";
import assert from "node:assert/strict";
import { insertionSort } from "./insertionSort.ts";

test("example", () => {
  assert.deepEqual(insertionSort([5, 2, 4, 6, 1, 3]), [1, 2, 3, 4, 5, 6]);
});

test("edges", () => {
  assert.deepEqual(insertionSort([]), []);
  assert.deepEqual(insertionSort([1]), [1]);
  assert.deepEqual(insertionSort([3, 2, 1, 1]), [1, 1, 2, 3]);
  assert.deepEqual(insertionSort(["pear", "fig", "apple"]), ["apple", "fig", "pear"]);
});

test("random against Array.prototype.sort", () => {
  let s = 2150;
  const next = (m: number): number => {
    s = (Math.imul(s, 1103515245) + 12345) >>> 0;
    return (s >>> 8) % m;
  };
  for (let t = 0; t < 500; t++) {
    const a = Array.from({ length: next(41) }, () => next(101) - 50);
    const want = [...a].sort((p, q) => p - q);
    assert.deepEqual(insertionSort([...a]), want);
  }
});

insertion_sort.gotests passPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.

// Package insertionsort sorts a slice by insertion.
package insertionsort

import "cmp"

// Sort sorts a in place, in non-decreasing order. The sort is stable.
func Sort[T cmp.Ordered](a []T) {
	for i := 1; i < len(a); i++ { // @line L1
		key := a[i]                  // @line L2
		j := i - 1                   // @line L3
		for j >= 0 && a[j] > key {   // @line L4
			a[j+1] = a[j] // @line L5
			j--           // @line L6
		}
		a[j+1] = key // @line L7
	}
}

insertion_sort_test.go 44 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.

package insertionsort

import (
	"math/rand/v2"
	"slices"
	"testing"
)

func TestExample(t *testing.T) {
	a := []int{5, 2, 4, 6, 1, 3}
	Sort(a)
	if !slices.Equal(a, []int{1, 2, 3, 4, 5, 6}) {
		t.Errorf("got %v", a)
	}
}

func TestEdges(t *testing.T) {
	for _, a := range [][]int{{}, {1}, {2, 1}, {1, 1, 1}, {3, 2, 1}} {
		b := slices.Clone(a)
		Sort(b)
		if !slices.IsSorted(b) {
			t.Errorf("Sort(%v) = %v", a, b)
		}
	}
}

func TestRandom(t *testing.T) {
	r := rand.New(rand.NewPCG(2150, 0))
	for range 500 {
		a := make([]int, r.IntN(41))
		for i := range a {
			a[i] = r.IntN(101) - 50
		}
		b, want := slices.Clone(a), slices.Clone(a)
		Sort(b)
		slices.Sort(want)
		if !slices.Equal(b, want) {
			t.Fatalf("Sort(%v) = %v", a, b)
		}
	}
}

insertion_sort.rstests passPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.

//! Insertion sort.

/// Sorts `a` in place, in non-decreasing order. The sort is stable.
pub fn insertion_sort<T: Ord + Clone>(a: &mut [T]) {
    for i in 1..a.len() {
        // @line L1
        let key = a[i].clone(); // @line L2
        let mut j = i; // @line L3: j is one more than in the pseudocode, so it stays unsigned
        while j > 0 && a[j - 1] > key {
            // @line L4
            a[j] = a[j - 1].clone(); // @line L5
            j -= 1; // @line L6
        }
        a[j] = key; // @line L7
    }
}

insertion_sort_test.rs 38 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.

use algo_insertion_sort::insertion_sort;

#[test]
fn example() {
    let mut a = [5, 2, 4, 6, 1, 3];
    insertion_sort(&mut a);
    assert_eq!(a, [1, 2, 3, 4, 5, 6]);
}

#[test]
fn edges() {
    let mut e: [i32; 0] = [];
    insertion_sort(&mut e);
    let mut a = [3, 2, 1, 1];
    insertion_sort(&mut a);
    assert_eq!(a, [1, 1, 2, 3]);
}

#[test]
fn random_against_std() {
    let mut s: u64 = 2150;
    let mut next = |m: u64| {
        s = s.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
        (s >> 33) % m
    };
    for _ in 0..500 {
        let n = next(41) as usize;
        let a: Vec<i64> = (0..n).map(|_| next(101) as i64 - 50).collect();
        let mut b = a.clone();
        let mut want = a.clone();
        insertion_sort(&mut b);
        want.sort();
        assert_eq!(b, want);
    }
}

InsertionSort.ktPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.

/** Sorts a in place, in non-decreasing order. The sort is stable. */
fun <T : Comparable<T>> insertionSort(a: MutableList<T>) {
    for (i in 1 until a.size) { // @line L1
        val key = a[i] // @line L2
        var j = i - 1 // @line L3
        while (j >= 0 && a[j] > key) { // @line L4
            a[j + 1] = a[j] // @line L5
            j-- // @line L6
        }
        a[j + 1] = key // @line L7
    }
}

InsertionSortTest.kt 36 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.

import kotlin.random.Random
import org.junit.jupiter.api.Assertions.assertEquals
import org.junit.jupiter.api.Test

class InsertionSortTest {
    @Test
    fun example() {
        val a = mutableListOf(5, 2, 4, 6, 1, 3)
        insertionSort(a)
        assertEquals(listOf(1, 2, 3, 4, 5, 6), a)
    }

    @Test
    fun edges() {
        val e = mutableListOf<Int>()
        insertionSort(e)
        assertEquals(emptyList<Int>(), e)
        val w = mutableListOf("pear", "fig", "apple")
        insertionSort(w)
        assertEquals(listOf("apple", "fig", "pear"), w)
    }

    @Test
    fun randomAgainstSorted() {
        val rng = Random(2150)
        repeat(500) {
            val a = MutableList(rng.nextInt(41)) { rng.nextInt(101) - 50 }
            val want = a.sorted()
            insertionSort(a)
            assertEquals(want, a)
        }
    }
}

References

Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, fourth edition, Section 2.1
Donald E. Knuth, The Art of Computer Programming, Volume 3, second edition, Section 5.2.1, Algorithm S

i	key	the array after the step
start		5 \| 2 4 6 1 3
1	2	2 5 \| 4 6 1 3
2	4	2 4 5 \| 6 1 3
3	6	2 4 5 6 \| 1 3
4	1	1 2 4 5 6 \| 3
5	3	1 2 3 4 5 6 \|

Ladder	Level	What the next level needs
Human proof		a full proof of time.average a full proof of time.best a full proof of time.total a full proof of time.worst a full proof of space.extra
Lean		name a Lean module in the lean field (07)
Code (c)		I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (cpp)		I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (csharp)		the native tests did not run in this build I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (go)		I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (java)		the native tests did not run in this build I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (javascript)		I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (kotlin)		the native tests did not run in this build I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (python)		I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (rust)		I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (typescript)		I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Visual		V2 needs the oracle check V03, line-trace agreement V06, the counter check V07 and the budgets V08 (10.8.2)
Writing		the lead paragraph

Insertion sort

In plain words

See it run

The problem

The algorithm

Example

Correctness

Complexity

Properties

Variants and improvements

When to use it

Pitfalls

Implementations

References

Where this leads

About this page

In plain words

See it run

The problem

The algorithm

Example

Correctness

Complexity

Properties

Variants and improvements

When to use it

Pitfalls

Implementations

References

Where this leads

Related

About this page