Sorting Algorithms

Step-by-step reference
Input Array
[ 5, 2, 9, 1, 5, 6 ]
Current / Key
Comparing
Sorted / Fixed
Pivot
Unsorted
01
Bubble Sort
O(n²) · stable
Compare adjacent pairs, swap if out of order. After each pass the largest unsorted element settles at the right end.
Start
5
2
9
1
5
6
Pass 1
2
5
1
5
6
9
Pass 2
2
1
5
5
6
9
Pass 3
1
2
5
5
6
9
Pass 4
1
2
5
5
6
9
Pass 4 performs no swaps → early-exit optimization terminates here. Sorted: [1, 2, 5, 5, 6, 9]
02
Selection Sort
O(n²) · not stable
Find the minimum in the unsorted suffix, swap it into the leftmost unsorted position.
Start
5
2
9
1
5
6
Step 1
1
2
9
5
5
6
Step 2
1
2
9
5
5
6
Step 3
1
2
5
9
5
6
Step 4
1
2
5
5
9
6
Step 5
1
2
5
5
6
9
Sorted
1
2
5
5
6
9
Step 3 swaps positions 2↔3, reordering the two 5s relative to each other — this is why selection sort is not stable.
03
Insertion Sort
O(n²) · stable
Grow a sorted prefix on the left by inserting each new element into its correct position.
Start
5
2
9
1
5
6
Insert 2
2
5
9
1
5
6
Insert 9
2
5
9
1
5
6
Insert 1
1
2
5
9
5
6
Insert 5
1
2
5
5
9
6
Insert 6
1
2
5
5
6
9
Comparison stops on the first ≤ match → original order of equal 5s is preserved (stable). Sorted: [1, 2, 5, 5, 6, 9]
04
Merge Sort
O(n log n) · stable
Recursively split the array in half until single elements remain, then merge sorted halves bottom-up.
5
2
9
1
5
6
▼ split ▼
5
2
9
1
5
6
▼ split ▼
5
2
9
1
5
6
▼ split ▼
5
2
9
1
5
6
▲ merge ▲
2
5
9
1
5
6
▲ merge ▲
2
5
9
1
5
6
▲ merge ▲
1
2
5
5
6
9
During the final merge, ties (5 vs 5) take the left value first → preserves stability.
05
Quick Sort
O(n log n) · not stable
Choose a pivot, partition into < pivot, = pivot, > pivot, recurse on the outer groups.
Start
5
2
9
1
5
6
Partition
pivot=6
5
2
1
5
6
9
Recurse L
pivot=5
2
1
5
5
Recurse
[2,1]
1
2
Combine L
1
2
5
5
Recurse R
9
Combine
1
2
5
5
6
9
Three-way partition keeps elements equal to the pivot with the pivot → avoids the ambiguity of where duplicate keys belong.
06
Heap Sort
O(n log n) · not stable
Build a max-heap, then repeatedly swap root with last element and sift down the shrinking heap.
9 5 6 1 2 5
Max-heap
(array)
9
5
6
1
2
5
Swap 9↔5
heapify
6
5
5
1
2
9
Swap 6↔2
heapify
5
2
5
1
6
9
Swap 5↔1
heapify
5
2
1
5
6
9
Swap 5↔1
heapify
2
1
5
5
6
9
Swap 2↔1
1
2
5
5
6
9
All 6 nodes present in the tree. Five swap-and-heapify iterations produce the sorted array in place.
07
Counting Sort
O(n + k) · stable
Count each value's occurrences, compute cumulative counts, then place each element at its correct index.
Value (1..9)
1
2
3
4
5
6
7
8
9
Count
1
1
0
0
2
1
0
0
1
Prefix sum
1
2
2
2
4
5
5
5
6
Input
5
2
9
1
5
6
Place
(R→L)
1
2
5
5
6
9
Iterating input right-to-left and decrementing prefix-sum slots preserves relative order of equal keys → stable.
08
Radix Sort (LSD)
O(n · k) · stable
Sort by each digit position from least to most significant using a stable inner sort (here: counting sort).
Input
170
45
75
90
Pass 1
ones digit
170
90
45
75
Pass 2
tens digit
45
170
75
90
Pass 3
hundreds
45
75
90
170
Pass 1 ones digits: 0,5,5,0 → stable tie-break keeps 170 before 90, 45 before 75.
Pass 2 tens digits: 7,9,4,7 → sort gives 4,7,7,9; stable tie-break keeps 170 before 75.
Pass 3 hundreds: 0,1,0,0 → 170 sinks to the end. Sorted: [45, 75, 90, 170]