Insertion Sort is another simple to understand and implement algorithm. Unlike Selection Sort it can work faster with certain data.

The algorithm is very simple:

1. Start from the second element and iterate to the end of array.
2. Slide all greater elements to the right by one position.
3. Insert the element from #1 into empty space made by #2.

• the worst case (array sorted in reverse order) running time is ϴ(n²) (Big Theta n²)
• the best case (sorted array) running time is ϴ(n) (Big Theta n²)
• memory complexity in O(1), because the algorithm reuses the same array.

package com.farenda.tutorials.algorithms.sorting;

public class InsertionSorter {

    public void sort(int[] values) {
        for (int i = 1; i < values.length; ++i) {
            insert(values, i-1, values[i]);
        }
    }

    private void insert(int[] array, int rightIndex, int value) {
        while (0 <= rightIndex && value < array[rightIndex]) {
            array[rightIndex+1] = array[rightIndex];
            --rightIndex;
        }
        array[rightIndex+1] = value;
    }
}

Let’s verify the implementation with a few JUnit tests:

package com.farenda.tutorials.algorithms.sorting;

import org.junit.Test;

import static org.junit.Assert.assertArrayEquals;

public class InsertionSortTest {

    private InsertionSorter sorter = new InsertionSorter();

    @Test
    public void shouldDoNothingWithEmptyArray() {
        int[] values = {};

        sorter.sort(values);
    }

    @Test
    public void shouldDoNothingWithOneElementArray() {
        int[] values = {42};

        sorter.sort(values);

        assertArrayEquals(new int[] {42}, values);
    }

    @Test
    public void shouldSortValues() {
        int[] values = { 9, -3, 5, 0, 1};
        int[] expectedOrder = { -3, 0, 1, 5, 9};

        sorter.sort(values);

        assertArrayEquals(expectedOrder, values);
    }
}

• Compare with Selection Sort