Quick sort: pick a pivot, move everything smaller to its left, then recurse on each side.
Usually the fastest in practice thanks to cache behaviour, but the worst case is real without a good pivot.
| On this exact input | Comparisons | Writes | Worst case |
|---|---|---|---|
| Bubble sort | 117 | 114 | O(n²) |
| Selection sort | 120 | 26 | O(n²) |
| Insertion sort | 69 | 72 | O(n²) |
| Merge sort | 46 | 64 | O(n log n) |
| Quick sort | 42 | 46 | O(n²) |
| Heap sort | 85 | 112 | O(n log n) |
| Counting sort | 0 | 16 | O(n + k) |
Counting sort runs on a smaller value range than the others, since it needs one bucket per distinct value.