Insertion Sort
Overview
Insertion Sort is a simple, intuitive sorting algorithm. It builds the final sorted array one item at a time. It works exactly how most humans sort a hand of playing cards: you take one card, compare it to the sorted cards in your hand, and insert it into its exact correct position.
Algorithmically, it conceptually divides the array into two parts: a 'sorted' left half and an 'unsorted' right half. It iterates through the unsorted half, takes an element, and shifts all larger elements in the sorted half to the right to make room for it.
While its worst-case time complexity is O(N^2), it is remarkably efficient for very small datasets or arrays that are already mostly sorted. In fact, modern hybrid sorting algorithms (like Java's default Arrays.sort(), which uses Timsort) switch to Insertion Sort under the hood when the array chunks get small enough (around 32 elements).
Syntax
public class Sort {
public static void insertionSort(int[] arr) {
// Start from index 1 (assume index 0 is initially 'sorted')
for (int i = 1; i < arr.length; i++) {
int key = arr[i]; // The item we want to insert
int j = i - 1;
// Move elements of arr[0..i-1] that are greater than key
// one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // Shift the larger element right
j = j - 1; // Move index backwards
}
// Insert the key into its correct sorted position
arr[j + 1] = key;
}
}
}Common Pitfalls
- Using standard swapping instead of shifting. While you can implement insertion sort by continuously swapping the key with the element before it, shifting is faster. Shifting only requires one assignment per comparison (
arr[j+1] = arr[j]), whereas swapping requires three assignments (using a temp variable). - Going out of bounds. The inner while loop must always check
j >= 0BEFORE trying to accessarr[j]. If you swap the conditions toarr[j] > key && j >= 0, Java evaluates left-to-right, throws an ArrayIndexOutOfBoundsException whenjis -1, and crashes. - Using it for large datasets. Insertion sort is strictly O(N^2). If you use it on an array of 100,000 items, it will take billions of operations and visibly hang your application. It is only for small or nearly-sorted data.
Interview Questions
O(N). If the array is already perfectly sorted, the inner while loop condition (arr[j] > key) immediately fails every time. The outer loop runs N times, doing O(1) work each time. This makes it vastly superior to Selection Sort or Bubble Sort on nearly-sorted data.
Yes. A stable sort preserves the relative order of equal elements. Because the while loop only shifts elements that are strictly greater (>) than the key, an element will never jump ahead of another element with the exact same value.
Real-World Example
Timsort (the default sorting algorithm in Python and Java for Objects) splits massive arrays into tiny 'Runs' of 32-64 elements. It uses Insertion Sort to perfectly sort these tiny runs (because Insertion Sort is lightning fast on tiny arrays with zero overhead), and then uses Merge Sort to stitch the runs together.
// Conceptual snippet of how Timsort utilizes Insertion Sort
public void timSort(int[] arr) {
int RUN = 32;
// Sort tiny chunks using Insertion Sort
for (int i = 0; i < arr.length; i += RUN) {
insertionSort(arr, i, Math.min(i + RUN - 1, arr.length - 1));
}
// Merge the sorted chunks...
}Check Your Knowledge
Test your understanding of Insertion Sort with these quick questions.