Master insertion sort step by step. See how each element “inserts” into its correct place, watch a detailed dry run, and review commented Python code, intuition, and Big-O costs.
So let’s get started with the [Problem Link].
1. What does the algorithm do?
Insertion sort takes an array and builds the sorted list one item at a time, always keeping the left side already sorted.
Think about sorting a hand of playing cards:
- You look at the next card.
- You slide it left until it sits in the correct spot among the cards you have already arranged.
- Repeat until all cards are placed.
That is exactly how insertion sort works on numbers.
2. Quick examples
| Input array | Sorted output | How it happens |
|---|---|---|
[4, 3, 1, 2] | [1, 2, 3, 4] | 4 ✔ → insert 3 before 4 → insert 1 before 3 → insert 2 between 1 and 3 |
[1, 2, 3, 4] | [1, 2, 3, 4] | Already sorted, each element stays in place (best case). |
3. Intuition & approach
3.1 Inner picture
Imagine a vertical divider that separates the sorted left part from the unsorted right part.
[ sorted | unsorted ]- The divider starts after the first element (because a single item is trivially sorted).
- Each pass picks the first element in the unsorted side (
key). - Slide that
keyleft, shifting bigger elements right, until you find its correct spot. - Move the divider one step to the right and repeat.
3.2 Why it works
The algorithm maintains the loop invariant:
“Elements to the left of
iare always in non-decreasing order.”
After the final pass, the divider is at the very end, thus the whole array is sorted.
3.3 When is it useful?
- Small input sizes (the simple logic beats heavier algorithms).
- Lists that are almost sorted, Time Complexity drops to O(n) because the inner while-loop rarely runs.
- Situations where stability and in-place memory (
O(1)) are required.
Read about the Python Program to Implement Selection Sort Algorithm.
4. Python code
def insertion_sort(arr):
# Start from the second element; first element is a sorted sub-array of length 1
for i in range(1, len(arr)):
key = arr[i] # element we want to insert
j = i - 1 # index that scans the sorted part (left side)
# Shift larger elements one step to the right
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
# Place 'key' into its correct spot
arr[j + 1] = key5. Step-by-step code explanation
- Outer
forloop (ifrom 1 to n-1).imarks the boundary between sorted and unsorted parts. key = arr[i].
Save the element to be inserted.- Inner
whileloop.jwalks left across the sorted section.- As long as
arr[j]is bigger thankey, shiftarr[j]one cell to the right. - Stop when you find a number ≤
keyor hit the array’s start.
- Insert
key.
The correct position forkeyis just to the right of where the loop stopped (j + 1). - Repeat until the entire array is processed.
6. Complexity
| Case | Time | Why |
|---|---|---|
| Worst / Average | O(n²) | In reversed or random arrays, each new key may scan almost the whole sorted part. |
| Best | O(n) | If the array is already sorted, the while test fails immediately every time. |
| Space | O(1) | Sort happens in place; only a few variables (key, i, j). |
7. Conclusion
Insertion sort is:
- Simple – only two loops and a handful of variables.
- Stable & in-place – keeps equal items in original order using no extra memory.
- Efficient for small or nearly-sorted data, though it scales quadratically in the worst case.
Remember the card-sorting analogy, and you’ll always recall how insertion sort inserts each element into its proper place.
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.
