Warning: Use of undefined constant fixed - assumed 'fixed' (this will throw an Error in a future version of PHP) in /home/webtro13/domains/farenda.com/public_html/wp-content/themes/moments/header.php on line 65

## Insertion Sort in Java

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

## How it works

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.

## Insertion Sort properties

• 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.

## Insertion Sort implementation

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;
}
}

## Unit tests

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);
}
}

## References:

Share with the World!