How it works
Any sort that works by comparing pairs needs at least n log n comparisons in the worst case, which is why merge sort is asymptotically optimal and bubble sort is not.
Classify a sort by its worst, average, and best case, and by whether it is stable and in place.
Common error
Quoting one complexity for a sort that has different worst and average behavior, as quick sort does.
Worked example
Java snippets run inside a main method. Add import java.util.*; when collection types are used.
Java
int[] a = {4, 1, 3};
for (int i = 1; i < a.length; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
a[j + 1] = key;
}
System.out.println(Arrays.toString(a));Output
[1, 3, 4]Insertion sort maintains a sorted prefix. Each pass saves one item, shifts larger prefix items right, and inserts the saved item into its ordered position.
Exercises
2.2.1 · Explain
Why is insertion sort linear on already-sorted input in this implementation?
Show solution
Each pass immediately fails the inner comparison, so there are only a constant number of operations per outer iteration.
2.2.2 · Explain
Does the greater-than comparison in the inner loop preserve equal-item order?
Show solution
Yes. Equal items are not shifted past each other, so this implementation is stable. Changing the comparison can change that property.