1. Overview
In this tutorial, we’re going to discuss the Insertion Sort algorithm and have a look at its Java implementation.
Insertion Sort is an efficient algorithm for ordering a small number of items. This method is based on the way card players sort a hand of playing cards.
We start with an empty left hand and the cards laid down on the table. We then remove one card at a time from the table and insert it into the correct position in the left hand. To find the correct position for a new card, we compare it with the already sorted set of cards in the hand, from right to left.
Let’s start by understanding the algorithm steps in pseudocode form.
2. Pseudocode
We’re going to present our pseudocode for insertion sort as a procedure called INSERTION-SORT, taking as parameter an array A[1 .. n] of n items to be sorted. The algorithm sorts the input array in-place (by rearranging the items within the array A).
After the procedure has finished, the input array A contains a permutation of the input sequence but in sorted order:
INSERTION-SORT(A)
for i=2 to A.length
key = A[i]
j = i - 1
while j > 0 and A[j] > key
A[j+1] = A[j]
j = j - 1
A[j + 1] = key
Let’s briefly go over the algorithm above.
The index i indicates the position of the current item in the array to process.
We begin from the second item as by definition an array with one item is considered to be sorted. The item at index i is called a key. Once having the key, the second part of the algorithm deals with finding its correct index. If the key is smaller than the value of the item at index j, then the key moves one position to the left. The process continues until the case when we reach an element being smaller than the key.
It’s important to note that before starting the iteration for finding the correct position of the key at index i, the array A[1 .. j – 1] is already sorted.
3. Imperative Implementation
For the imperative case, we’re going to write a function called insertionSortImperative, taking as a parameter an array of integers. The function starts iterating over the array from the second item.
At any given time during the iteration, we could think of this array as being logically divided into two portions; the left side being the sorted one and right side containing the items not yet sorted.
An important note here is that after finding the correct position at which we’ll insert the new item, we shift (and not swap) the items to the right to free a space for it.
public static void insertionSortImperative(int[] input) {
for (int i = 1; i < input.length; i++) {
int key = input[i];
int j = i - 1;
while (j >= 0 && input[j] > key) {
input[j + 1] = input[j];
j = j - 1;
}
input[j + 1] = key;
}
}
Next, let’s create a test for the method above:
@Test
void givenUnsortedArray_whenInsertionSortImperative_thenSortedAsc() {
int[] input = {6, 2, 3, 4, 5, 1};
InsertionSort.insertionSortImperative(input);
int[] expected = {1, 2, 3, 4, 5, 6};
assertArrayEquals("the two arrays are not equal", expected, input);
}
The test above proves that the algorithm sorts correctly in ascending order the input array <6, 2, 3, 4, 5, 1>.
4. Recursive Implementation
The function for the recursive case is called insertionSortR**ecursive and accepts as input an array of integers (same as for the imperative case).
The difference here from the imperative case (despite the fact that it’s recursive) is that it calls an overloaded function with a second argument that equals the number of items to sort.
As we want to sort the complete array, we’ll pass a number of items equal to its length:
public static void insertionSortRecursive(int[] input) {
insertionSortRecursive(input, input.length);
}
The recursive case is a little bit more challenging. The base case occurs when we attempt to sort an array with one item. In this case, we do nothing.
All the subsequent recursive calls sort a predefined portion of the input array – starting from the second item till we reach the end of the array:
private static void insertionSortRecursive(int[] input, int i) {
if (i <= 1) {
return;
}
insertionSortRecursive(input, i - 1);
int key = input[i - 1];
int j = i - 2;
while (j >= 0 && input[j] > key) {
input[j + 1] = input[j];
j = j - 1;
}
input[j + 1] = key;
}
And this is what the call stack looks like for an input array of 6 items:
insertionSortRecursive(input, 6)
insertionSortRecursive(input, 5) and insert the 6th item into the sorted array
insertionSortRecursive(input, 4) and insert the 5th item into the sorted array
insertionSortRecursive(input, 3) and insert the 4th item into the sorted array
insertionSortRecursive(input, 2) and insert the 3rd item into the sorted array
insertionSortRecursive(input, 1) and insert the 2nd item into the sorted array
Let’s also see the test for it:
@Test
void givenUnsortedArray_whenInsertionSortRecursively_thenSortedAsc() {
int[] input = {6, 4, 5, 2, 3, 1};
InsertionSort.insertionSortRecursive(input);
int[] expected = {1, 2, 3, 4, 5, 6};
assertArrayEquals("the two arrays are not equal", expected, input);
}
The test above proves that the algorithm sorts correctly in ascending order the input array <6, 2, 3, 4, 5, 1>.
5. Time and Space Complexity
The time taken by the INSERTION-SORT procedure to run is O(n^2). For each new item, we iterate from right to left over the already sorted portion of the array to find its correct position. Then we insert it by shifting the items one position to the right.
The algorithm sorts in place so its space complexity is O(1) for the imperative implementation and O(n) for the recursive implementation.
6. Conclusion
In this tutorial, we saw how to implement insertion sort.
This algorithm is useful for sorting a small number of items. It becomes inefficient when sorting input sequences having more than 100 items.
Keep in mind that despite its quadratic complexity it sorts in place without the need of auxiliary space as is the case for merge sort.
The entire code could be found over on GitHub.