Fundamentals · Medium · Free
Why is insertion sort useful for small or nearly sorted arrays?
FresherFundamentalsData Structures & Algorithms
Insertion sort
Build sorted prefix by inserting each element into correct position—O(n²) worst, O(n) on nearly sorted data. Stable, in-place, great for small n.
java
void insertionSort(int[] a) {
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;
}
}Java's
Arrays.sort uses insertion sort for small subarrays.