Sorting
Heap sort vs Radix sort
Heap sort and Radix sort both put an array in order, in different ways. Heap sort: build a max-heap in the array, then repeatedly move the largest value to the end. Radix sort: sort digit by digit, least significant first, with a stable counting sort for each digit. Radix sort compares no values: it takes O(d (n + k)), where k is the number of possible values (or digit values) and d the number of digits (radix sort), while heap sort takes O(n log n) in the worst case. Radix sort is faster only when k and d are small compared with n; heap sort makes no assumption about the values.
At a glance
| Property | Heap sort | Radix sort |
|---|---|---|
| Technique | Build a max-heap in the array, then repeatedly move the largest value to the end | Sort digit by digit, least significant first, with a stable counting sort for each digit |
| Compares values with each other | Yes | No |
| Best case time | O(n log n) | O(d (n + k)) |
| Average case time | O(n log n) | O(d (n + k)) |
| Worst case time | O(n log n) | O(d (n + k)) |
| Extra space | O(1) | O(n + k) |
| Stable (equal values keep their order) | No | Yes |
| In place (no extra array) | Yes | No |
| Needs sorted input | No | No |
When to choose each
Choose heap sort when
you need a guaranteed O(n log n) time and almost no extra memory.
Avoid it when
you need a stable sort, or the fastest sort on typical data.
Choose radix sort when
many integers or fixed-length keys have few digit positions (d is small).
Avoid it when
the array is small, or the keys are long.
The same inputs, counted
These numbers come from running both real implementations: operations (comparisons plus writes, a swap counting as two writes). Radix sort makes no comparisons, so its count is writes only. The lesson always runs 3 digit passes, even on these one-digit numbers.
| Input | Heap sort | Radix sort |
|---|---|---|
| Mixed | 43 | 141 |
| Already sorted | 53 | 141 |
| Reversed | 40 | 141 |
| Nearly sorted | 50 | 141 |
| Duplicates | 36 | 141 |
See them run
More comparisons
- Bubble sort vs Selection sort
- Bubble sort vs Insertion sort
- Bubble sort vs Merge sort
- Bubble sort vs Quick sort
- Bubble sort vs Heap sort
- Bubble sort vs Counting sort
- Bubble sort vs Radix sort
- Selection sort vs Insertion sort
- Selection sort vs Merge sort
- Selection sort vs Quick sort
- Selection sort vs Heap sort
- Selection sort vs Counting sort
- Selection sort vs Radix sort
- Insertion sort vs Merge sort
- Insertion sort vs Quick sort
- Insertion sort vs Heap sort
- Insertion sort vs Counting sort
- Insertion sort vs Radix sort
- Merge sort vs Quick sort
- Merge sort vs Heap sort
- Merge sort vs Counting sort
- Merge sort vs Radix sort
- Quick sort vs Heap sort
- Quick sort vs Counting sort
- Quick sort vs Radix sort
- Heap sort vs Counting sort
- Counting sort vs Radix sort