Sorting
Quick sort vs Heap sort
Quick sort and Heap sort both put an array in order, in different ways. Quick sort: divide and conquer: partition around a pivot. Heap sort: build a max-heap in the array, then repeatedly move the largest value to the end. In the worst case heap sort takes O(n log n) while quick sort takes O(n²), so heap sort scales better on large inputs.
At a glance
| Property | Quick sort | Heap sort |
|---|---|---|
| Technique | Divide and conquer: partition around a pivot | Build a max-heap in the array, then repeatedly move the largest value to the end |
| Best case time | O(n log n) | O(n log n) |
| Average case time | O(n log n) | O(n log n) |
| Worst case time | O(n²) | O(n log n) |
| Extra space | O(log n) | O(1) |
| Stable (equal values keep their order) | No | No |
| In place (no extra array) | Yes | Yes |
| Needs sorted input | No | No |
When to choose each
Choose quick sort when
you want a fast in-place sort on typical data.
Avoid it when
you need a worst-case guarantee or a stable sort.
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.
The same inputs, counted
These numbers come from running both real implementations: operations (comparisons plus writes, a swap counting as two writes).
| Input | Quick sort | Heap sort |
|---|---|---|
| Mixed | 31 | 43 |
| Already sorted | 75 | 53 |
| Reversed | 51 | 40 |
| Nearly sorted | 65 | 50 |
| Duplicates | 29 | 36 |
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 Counting sort
- Quick sort vs Radix sort
- Heap sort vs Counting sort
- Heap sort vs Radix sort
- Counting sort vs Radix sort