Insertion Sort

// Insertion Sort (Zerethon Official Sample: insertion-sort 1.1.0).
// The algorithm as shown in Zerethon Tools.
public class InsertionSort {
    static void insertionSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int key = a[i], j = i - 1;
            while (j >= 0 && a[j] > key) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = key;
        }
    }
}

// Checks for insertionSort. To run them, set this file as the entry file
// (the ▶ button next to it in Files) and press Run.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class InsertionSortTest {
    /** Deterministic pseudo-random integers in [-50, 49] (the same as the Python checks). */
    static int[] numbers(long seed, int count) {
        int[] out = new int[count];
        for (int i = 0; i < count; i++) {
            seed = (seed * 1103515245L + 12345L) % 2147483648L;
            out[i] = (int) (seed % 100) - 50;
        }
        return out;
    }

    public static void main(String[] args) {
        List<int[]> cases = new ArrayList<>(List.of(
            new int[] {}, new int[] {1}, new int[] {2, 1}, new int[] {1, 2, 3}, new int[] {3, 2, 1},
            new int[] {5, 1, 5, 1, 5}, new int[] {-3, 0, -1, 2}));
        cases.add(numbers(1, 10));
        cases.add(numbers(2, 50));
        cases.add(numbers(3, 200));

        for (int[] c : cases) {
            int[] result = c.clone();
            InsertionSort.insertionSort(result);
            int[] expected = c.clone();
            Arrays.sort(expected);
            if (!Arrays.equals(result, expected)) {
                System.err.println("insertionSort(" + Arrays.toString(Arrays.copyOf(c, Math.min(6, c.length))) + "...) = " + Arrays.toString(result));
                System.exit(1);
            }
        }
        System.out.println("All " + cases.size() + " checks passed.");
    }
}

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] numbers = {38, 27, 43, 3, 9, 82, 10, 27};
        System.out.println("Before: " + Arrays.toString(numbers));
        int[] result = numbers.clone();
        InsertionSort.insertionSort(result);
        System.out.println("After:  " + Arrays.toString(result));
        int[] expected = numbers.clone();
        Arrays.sort(expected);
        System.out.println("Same as Arrays.sort(): " + Arrays.equals(result, expected));
    }
}

# Insertion Sort

Zerethon Official Sample `insertion-sort`, version 1.1.0, Java 25.

- `InsertionSort.java` — the algorithm, as shown in Zerethon Tools
- `Main.java` — entry file: a short demonstration
- `InsertionSortTest.java` — checks; set it as the entry file to run them

Every `.java` file is compiled together before the entry file's class runs.

This project is your own copy. Changing it never changes the official sample.
See the algorithm animated: https://tools.zerethon.com/insertion-sort-visualizer