Insertion Sort
Insertion Sort is a simple, comparison-based sorting algorithm that builds a sorted array one element at a time. The idea is very close to how most people sort a hand of playing cards: you pick up a card and slide it into its correct place among the cards you're already holding, so the "hand" stays sorted after every pick.
Insertion Sort divides the array into two logical parts:
- A sorted part (starts with just the first element).
- An unsorted part (the rest of the array).
On every step, the algorithm picks the first element of the unsorted part (called the key) and inserts it into its correct position inside the sorted part.
How Insertion Sort Works?
- Start from the second element of the array (index 1). The first element alone is trivially "sorted."
- Store this element in a variable called
key. - Compare
keywith the elements before it, moving from right to left. - Shift every element that is greater than
keyone position to the right. - Insert
keyinto the gap created. - Repeat this for every element until the end of the array is reached.
Example: Sorting [7, 4, 9, 2, 5]
Initial array: [7, 4, 9, 2, 5]
Pass 1 (i = 1), key = 4
- Compare 4 with 7 → 4 < 7, shift 7 right
- Insert 4 at index 0
- Array:
[4, 7, 9, 2, 5]
Pass 2 (i = 2), key = 9
- Compare 9 with 7 → 9 > 7, no shift needed
- Array unchanged:
[4, 7, 9, 2, 5]
Pass 3 (i = 3), key = 2
- Compare 2 with 9 → shift 9 right
- Compare 2 with 7 → shift 7 right
- Compare 2 with 4 → shift 4 right
- Insert 2 at index 0
- Array:
[2, 4, 7, 9, 5]
Pass 4 (i = 4), key = 5
- Compare 5 with 9 → shift 9 right
- Compare 5 with 7 → shift 7 right
- Compare 5 with 4 → 5 > 4, stop
- Insert 5 at index 2
- Array:
[2, 4, 5, 7, 9]
Final Sorted Array: [2, 4, 5, 7, 9]
| Pass | Key | Action | Resulting Array |
|---|---|---|---|
| 1 | 4 | shift 7, insert 4 at start | [4, 7, 9, 2, 5] |
| 2 | 9 | no shift needed | [4, 7, 9, 2, 5] |
| 3 | 2 | shift 9, 7, 4; insert at start | [2, 4, 7, 9, 5] |
| 4 | 5 | shift 9, 7; insert after 4 | [2, 4, 5, 7, 9] |
Pseudocode
Step 1: Start
Step 2: For i = 1 to n-1, repeat steps 3 to 6
Step 3: key = array[i]
Step 4: j = i - 1
Step 5: While j >= 0 and array[j] > key:
array[j+1] = array[j]
j = j - 1
Step 6: array[j+1] = key
Step 7: EndAdvantages
- Very simple to understand and implement.
- Efficient for small datasets.
- Stable sort — equal elements keep their original relative order.
- Adaptive — performs extremely well on data that is already nearly sorted (Best Case: O(n)).
- Works in-place, requiring no extra array.
- Good for online sorting — it can sort data as it arrives, one item at a time.
Disadvantages
- Very inefficient on large datasets compared to O(n log n) algorithms.
- Requires many shifting operations for reverse-sorted data.
- Not suitable when performance on large, randomly ordered data matters.
Time and Space Complexity
| Case | Time Complexity | Explanation |
|---|---|---|
| Best Case | O(n) | Array is already sorted; only one comparison per element, no shifting |
| Average Case | O(n²) | Elements are in random order |
| Worst Case | O(n²) | Array is sorted in reverse order; every element must shift all the way to the front |
Space Complexity: O(1) — Insertion Sort sorts in-place and needs only a constant amount of extra memory (for the key and loop variables).
Stability: Stable In-place: Yes
When to Use Insertion Sort?
- Small arrays or lists.
- Data that is already mostly sorted.
- As a sub-routine inside hybrid algorithms (e.g., TimSort, IntroSort use Insertion Sort for small partitions).
- When stability of equal elements matters.
Practice Questions
- Sort the array
[8, 5, 2, 9, 1]using Insertion Sort and show the array after every pass. - For the array
[6, 4, 2, 8, 5], count the total number of comparisons made during a full Insertion Sort. - Sort
[10, 9, 8, 7, 6]using Insertion Sort. How many shift operations are performed in total? - If Insertion Sort is applied to an already sorted array of 20 elements, how many comparisons will be made in total?
- Trace through Insertion Sort for the array
[3, 3, 2, 1]and explain why Insertion Sort is called a "stable" algorithm using this example. - For the array
[15, 2, 30, 4, 25], identify the key and the shifts that occur during Pass 3 (i = 3). - Explain what happens to the time complexity of Insertion Sort if the input array has only 2 distinct values repeated many times.
- Write a program (in any language of your choice) to implement Insertion Sort and count the number of shift operations for a user-given array.
- Given the array
[40, 10, 30, 20], sort it manually using Insertion Sort and calculate the total number of comparisons and shifts separately.
Was this article helpful?