What is Insertion Sort?
Learn how insertion sort builds a sorted prefix by shifting elements, with O(n) best case and O(n^2) worst case.
Expected Interview Answer
Insertion sort builds the final sorted array one element at a time by taking each new element and shifting it leftward past every larger already-sorted element until it lands in its correct position, giving O(n^2) worst-case time but O(n) time on nearly sorted data and O(1) extra space.
The algorithm treats the array as split into a sorted prefix on the left and an unprocessed suffix on the right; each step takes the first element of the unprocessed suffix, compares it backward against the sorted prefix, and shifts larger elements one slot right until it finds the correct gap to drop the new element into. Because it only ever swaps adjacent-style shifted elements and never jumps across the array, it is naturally stable, and because it works entirely within the original array, it needs only O(1) extra space. Its real strength is on small or already nearly-sorted inputs, where the number of shifts per element is tiny, giving it a best case of O(n) — which is why many production sort implementations (like Timsort) fall back to insertion sort for small subarrays. On random or reverse-sorted data, though, each new element can require shifting past nearly the whole sorted prefix, giving the O(n^2) worst case shared with bubble sort and selection sort.
- O(n) best case on already or nearly sorted data
- Stable, preserving the relative order of equal elements
- O(1) extra space, fully in place
- Simple, low-overhead choice for small arrays or online/streaming insertion
AI Mentor Explanation
A statistician building a ranked list of batting averages one player at a time takes each new player and slides them leftward past every already-ranked player with a higher average, stopping the instant they find someone with an equal or higher average just ahead of them. If the new player’s average is already lower than everyone processed so far, only a couple of comparisons are needed before they slot into place near the end. But if the new player suddenly has the highest average of the season, they have to be walked all the way past every single player already ranked, which is the expensive case. Because each player only ever displaces others by one position at a time and never leapfrogs, two players with the exact same average always keep their original relative order.
Step-by-Step Explanation
Step 1
Start with a one-element sorted prefix
Treat the first element as trivially sorted; everything after it is the unprocessed suffix.
Step 2
Pick the next unprocessed element
Take the first element of the unprocessed suffix as the current "key" to insert.
Step 3
Shift larger elements rightward
Compare the key backward against the sorted prefix, shifting each larger element one slot right.
Step 4
Drop the key into the gap
Once a smaller-or-equal element (or the array start) is found, place the key there and repeat for the next element.
What Interviewer Expects
- Explain the sorted-prefix / unprocessed-suffix mental model
- State O(n^2) worst case, O(n) best case on nearly sorted data, and O(1) space
- Note that it is stable because elements never jump past equal elements
- Mention its practical use for small subarrays inside hybrid sorts like Timsort
Common Mistakes
- Claiming insertion sort is always O(n^2) without acknowledging its O(n) best case
- Confusing insertion sort with selection sort (selection sort scans for the minimum instead of shifting)
- Forgetting that the shifting step, not just comparison, is what makes the worst case quadratic
- Assuming it needs extra memory, when it sorts entirely in place
Best Answer (HR Friendly)
“Insertion sort builds up a sorted section of the array one element at a time, sliding each new element backward past larger elements until it lands in the right spot. It is not the fastest algorithm on random data, but it is simple, stable, and actually very efficient when the data is already close to sorted, which is why some hybrid sorting libraries use it for small chunks.”
Code Example
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arrFollow-up Questions
- Why does insertion sort perform well on nearly sorted arrays?
- How is insertion sort different from selection sort in what it does each iteration?
- Why do hybrid sorts like Timsort fall back to insertion sort for small subarrays?
- How would you count the number of shifts to measure how "unsorted" an array is?
MCQ Practice
1. What is insertion sort’s best-case time complexity?
On an already sorted array, each element requires only one comparison and no shifts, giving O(n) total.
2. Is insertion sort a stable sorting algorithm?
The shifting loop stops at the first element that is not strictly greater than the key, so equal elements never cross each other.
3. What extra space does insertion sort require?
Insertion sort shifts elements within the original array using one temporary variable for the key, needing only O(1) extra space.
Flash Cards
What is insertion sort’s worst-case time complexity? — O(n^2), when every new element must shift past nearly the whole sorted prefix.
What is insertion sort’s best-case time complexity? — O(n), on an already sorted or nearly sorted array.
Is insertion sort stable? — Yes, because elements only shift past strictly greater elements, never past equal ones.
Why do hybrid sorts use insertion sort for small subarrays? — Its low overhead makes it faster than O(n log n) algorithms once the subarray is small enough.