Insertion Sort: Implementation and Analysis

Insertion Sort

Overview
Insertion sort is simple, but poorly performing sort algorithm that can sort a list in place. The Insertion sort algorithm works by splitting the input list into two partitions; a sorted part and an unsorted part. At the start of Insertion sort, the sorted part consists of 1 item; the first item in the input. Insertion sort then takes the first item of the unsorted part and compares it with each item in the sorted list until it finds the item’s sorted position. Inserting the item into the list requires that items are shifted to make make room for the newly sorted item.

The following image from commons.wikimedia.com helps to visualize Insertion sort:

The Implementation
Here is Java code for the Insertion Sort algorithm.

[code language=”Java”]
public static void insertionSort(String in) {
char[] chars = in.toCharArray();

for (int ui=1; ui < chars.length; ui++) {
char uc = chars[ui];
int split = ui;
for (int si=split-1; si >= 0; si–) {
if (chars[si] < uc) {
// insert and shift
char tmp = chars[si];
chars[si] = uc;
chars[split–] = tmp;
} else {
// nothing to sort break
break;
}
}
}
System.out.println(chars);
}
[/code]

The Analysis
The outer for loops executes n-1 times while the inner loop also executes n-1 times, thus we execute:
(n-1) + (n-2) + ... + 1 = n * (n-1)/2 or O(n^2)

Insertion sort time complexity:
Worst case: O(n^2) – The list is sorted in reverse and every inner loop comparison also requires a shift.
Avg case: O(n^2) – We perform the comparisons, but shifts are not always required
Best case: O(n) – the entire list is sorted, the inner loop breaks immediately, thus n-1 items are compared.

Thank you!