Insertion Sort Algorithm

Description

Insertion Sort is one of the simplest, but not very effective, sorting algorithms . It works very similar to the way (us humans) sort a hand of playing cards:

1. At first none of our cards are sorted . So we start with an "empty" space in our hand were we are going to insert cards one at a time .

2. We take a card from our hand and we put it in the "special place" were we planned to keep our cards sorted . We do this for every card in our initial hand, until we finish them off .

3. Finding the right position for the insertion is not hard . At this point we can apply two tactics : We compare the card we are planning to insert with all the cards that are already in sorted state O(n); We use binary search to determine the right position (O(logn)) .

In our case that “special place” were we are going to insert cards one at a time, is not an additional array, but the array itself . We know for sure that an array of size 1 is always sorted, so we consider that first sorted sub-array, is the block composed by the first element .

For example, we want to sort the following array (with bold, are the elements already sorted):

8	0	3	11	5	-1	14	10	1	1	-2	Array is unsorted .
8	0	3	11	5	-1	14	10	1	1	-2	The first sorted block is {8} .
0	8	3	11	5	-1	14	10	1	1	-2	We compare {0} with {8} we move {0} at the new position, we shift {8} .
0	3	8	11	5	-1	14	10	1	1	-2	We compare {3} with {8}, {0}, we move {3} at the new position, we shift {8} .
0	3	8	11	5	-1	14	10	1	1	-2	We compare {11} with {8}, {11} remains at the same position .
0	3	5	8	11	-1	14	10	1	1	-2	We compare {5} with {11}, {8} and {3}, we move {5} at the new position, we shift {8}, {11} .
-1	0	3	5	8	11	14	10	1	1	-2	We compare {-1} with {11}, {8}, ..., {0}, we move {-1} at the new position, we shift {0}, {3}, ... {11} .
-1	0	3	5	8	11	14	10	1	1	-2	We compare {14} with {11}, we move {11} at the new position .
-1	0	3	5	8	10	11	14	1	1	-2	We compare {10} with {14}, {11}, {8}, we move {10} at the new position, we shift {11}, {14}.
-1	0	1	3	5	8	10	11	14	1	-2	We compare {1} with {14}, {11}, ..., {0}, we move {1} at the new position, we shift {3}, {5}, ..., {14} .
-1	0	1	1	3	5	8	10	11	14	-2	We compare {1} with {14}, {11}, ..., {1}, we move {1} at the new position, we shift {3}, {5}, ..., {14} .
-2	-1	0	1	1	3	5	8	10	11	14	We compare {-2} with {14}, {11}, ..., {-1}, we move {-2} at the new position, we shift {-1}, {0}, ..., {14} .

The pseudo-code for the algorithm can be easily written as follows:

FUNCTION SORT(A, length)
	// The array is 0-indexed
	FOR i:=1 TO length DO
		key := A[i]
		j := i - 1

		// COMPARE
		WHILE j >= 0 AND A[j] > key DO
			// SHIFT
			A[j+1] := A[j]
			j := j - 1

		// MOVE
		A[j+1] = key

Java Implementation

The Java implementation of the algorithm is pretty straight-forward:

public class InsertionSort {
	// Print array
	public static void printArray(int [] array){
		for(int i : array){
			System.out.printf("%d ", i);
		}
	}

	// Sort array through the 'Insertion Sort' method .
	public static void sortArray(int [] array){
		int key, j;
		for(int i = 1; i < array.length; ++i){
			key = array[i];
			j = i - 1;
			while(j >= 0 && array[j] > key){
				// Shift array elements so we can place
				// the key to the right place
				array[j+1] = array[j];
				j--;
			}
			// Place the key into position
			array[j+1] = key;
		}
	}

	public static void main(String[] args){
		int [] array = new int[] {8, 0, 3, 11, 5, -1 , 14, 10, 1, 1, -2};
		sortArray(array);
		printArray(array);
	}
}