In this tutorial, we are going to learn about insertion sort in detail and its algorithmic implementation.

Insertion Sort

• In-place algorithm.
• O(n^2) time complexity - Quadratic.
• It will take 100 steps to sort 10 items, 10000 steps to sort 100 items and 1000000 steps to sort 1000 items.
• Doesn’t require much swapping as bubble sort.
• Stable algorithm.

Insertion Sort Algorithm

INSERTION_SORT (A, N)

1. Set A[0] = -∞.
2. Repeat Step 3 to 5 for K = 2, 3, …, N:
3. Set TEMP = A[K] and PTR = K – 1.

4. Repeat while TEMP < A[PTR]:

   1. Set A[PTR+1] = A[PTR]
   2. Set PTR = PTR – 1. [End of Loop.]
5. Set A[PTR+1] = TEMP.
6. Return.

Insertion Sort Programmatic Implementation in Java

public class InsertionSort {
	public static void main(String[] args) {

		int[] intArray = { 20, 35, -15, 7, 55, 1, -22 };
		for (int firstUnsortedIndex = 1; firstUnsortedIndex < intArray.length; firstUnsortedIndex++) {
			int newElement = intArray[firstUnsortedIndex];
			int i;
			for (i = firstUnsortedIndex; i > 0 && intArray[i - 1] > newElement; i--) {
				intArray[i] = intArray[i - 1];
			}
			intArray[i] = newElement;
		}
		for (int i = 0; i < intArray.length; i++) {
			System.out.print(intArray[i]+ " ");
		}
	}}

Output:

-22 -15 1 7 20 35 55 

Insertion Sort Complexity

• This Sorting algorithm is frequently used when n is very small.

• Worst case occurs when array is in reverse order. The inner loop must use K – 1 comparisons.

  • f(n) = 1 + 2 + 3 + ….+ (n – 1) = n(n – 1)/2= O(n^2)

• In average case, there will be approximately (K – 1)/2 comparisons in the inner loop.

  • f(n) = 1 + 2 + 3 + ….+ (n – 1)/2 = n(n – 1)/4 = O(n^2)