Topic 49 of 78
Insertion Sort
Overview
Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It works exactly how you might sort playing cards in your hands: you take a new card and insert it into its correct position among the already sorted cards. While it has an O(N^2) worst-case time complexity, it is remarkably efficient for very small arrays or nearly sorted arrays.
Syntax
The left side of the array is always sorted. We pick up the next element and 'insert' it backward until it finds its proper place.
Standard Insertion Sort
java
public void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int currentElement = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1] that are greater than currentElement
// to one position ahead of their current position
while (j >= 0 && arr[j] > currentElement) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = currentElement;
}
}Common Pitfalls
- Using Insertion Sort on large, completely randomized arrays will be drastically slower than Merge Sort or Quick Sort.
- Making an off-by-one error on the inner while loop condition (`j >= 0`).
Interview Tips
- Best case time complexity is O(N) when the array is already sorted. Worst case is O(N^2). Space complexity is O(1).
Real-World Example
Java's own dual-pivot Quicksort (`Arrays.sort(int[])`) falls back to Insertion Sort when the remaining segment to sort is smaller than 47 elements.
example
java
// Conceptually how Java optimizes sorting
public void optimizedSort(int[] arr, int left, int right) {
if (right - left < 47) {
insertionSort(arr, left, right);
return;
}
quickSort(arr, left, right);
}