PCCST303 · Module 4: Sorting and Searching
Insertion Sort
Selection sort grows a sorted prefix by finding the minimum each time. Insertion sort grows the same kind of sorted prefix differently: it takes the next unsorted element and slides it leftward into its correct position among the already-sorted elements, the way a person sorts a hand of playing cards.
Idea
Definition
Insertion sort treats the array as a sorted part (front) and an unsorted part (rest). On each pass, it takes the first element of the unsorted part (KEY) and shifts every sorted element greater than KEY one position right, then places KEY into the gap that opens up.
Algorithm
INSERTION_SORT(A, N)
// A is the array to sort
// N is the number of elements in A
1. For i = 1 to N-1:
KEY = A[i]
j = i - 1
While j >= 0 AND A[j] > KEY:
A[j+1] = A[j]
j = j - 1
A[j+1] = KEY
2. Stop.Worked example
Sorting [29, 10, 14, 37, 14] in ascending order:
Pass 1 (i = 1). KEY = A[1] = 10. Compare with A[0] = 29: 29 > 10, shift it right, then place 10 in the opened gap:
Pass 2 (i = 2). KEY = A[2] = 14. Compare with A[1] = 29: 29 > 14, shift right. Compare with A[0] = 10: 10 < 14, stop shifting, place 14 right after 10:
Pass 3 (i = 3). KEY = A[3] = 37. Compare with A[2] = 29: 29 < 37, no shift needed, 37 is already in the right spot:
Pass 4 (i = 4). KEY = A[4] = 14. Compare with A[3] = 37: shift right. Compare with A[2] = 29: shift right. Compare with A[1] = 14: 14 > 14 is false (not strictly greater), stop, place 14 right after index 1:
Sorted.
The comparison uses strictly greater than (A[j] > KEY), not >=. This is what makes insertion sort stable: an equal element already in place is never shifted past, so two equal elements keep their original relative order.
Why it's fast on nearly-sorted input
Key Idea
Unlike selection sort, insertion sort's inner loop can stop early: as soon as it finds a sorted element that's already smaller than KEY, no more shifting is needed. On an already-sorted array, every pass does exactly one comparison and no shifts, giving O(N) best case.
Pass 3 above is a direct example: 37 needed zero shifts because it was already larger than everything before it.
Complexity
| Case | Complexity |
|---|---|
| Best (already sorted) | O(N), one comparison per pass, no shifts |
| Average | O(N²) |
| Worst (reverse sorted) | O(N²), every pass shifts all the way to index 0 |
| Space | O(1), sorts in place |
| Stability | Stable |
Selection sort vs insertion sort
| Feature | Selection sort | Insertion sort |
|---|---|---|
| Strategy | Find minimum, swap into place | Take next element, shift others to insert it |
| Comparisons | Always O(N²) | O(N) best, O(N²) worst |
| Swaps / shifts | At most N-1 swaps | Can shift many elements per pass |
| Stable | No | Yes |
| Good for | Minimizing writes | Nearly-sorted or small input |
Quick recall
- Grows a sorted prefix by taking the next element and shifting larger sorted elements right to make room for it.
- Best case
O(N)on already-sorted input (inner loop exits immediately); worst/average caseO(N²). - In-place,
O(1)extra space, and stable (uses strict>, never shifts past an equal element). - Faster in practice than selection sort on small or nearly-sorted arrays, despite the same worst-case order.