Insertion Sort works like sorting a hand of playing cards. It iterates through the array, and for each element it shifts larger elements one position right to make room, then inserts the current element. It is efficient for small arrays and nearly-sorted data, and is the basis of Tim Sort.
void insertionSort(vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; i++) {
int key = arr[i], j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}Insertion Sort maintains a sorted prefix. For each new element it scans backward through the sorted prefix, shifting elements right until the correct insertion point is found.
Insertion Sort is online: it can sort a list as it receives elements one by one without needing the full input upfront. This makes it ideal for streaming data scenarios.
When the array is nearly sorted, each element requires very few shifts. Best case is O(n) when the input is already sorted — only one comparison per element.
Insertion Sort is used for small subarrays (typically n < 16) in hybrid algorithms like Tim Sort and Intro Sort, where its low overhead beats the O(n log n) algorithms due to smaller constant factors.
Insertion Sort is most efficient when:
What is the worst-case time complexity of Insertion Sort?
Which real-world use case favors Insertion Sort?