Comparison sorts
Insertion, merge, quick and heap sort decide order by comparing keys. In the general model they need Ω(n log n) worst-case comparisons.
Algorithms · Sorting
Sorting algorithms
There is no universally best sorting algorithm. Key distribution, available memory, stability and input shape determine the right choice. Each card opens a visualizer for comparisons, movements and auxiliary structures.
Comparison table
| Algorithm | Best | Average | Worst | Auxiliary memory | Stable | In place |
|---|---|---|---|---|---|---|
| Insertion sort | Θ(n) | Θ(n²) | Θ(n²) | Θ(1) | Yes | Yes |
| Merge sort | Θ(n log n) | Θ(n log n) | Θ(n log n) | Θ(n) | Yes | No |
| Quicksort | Θ(n log n) | Θ(n log n) | Θ(n²) | Θ(log n)¹ | No | Yes |
| Heapsort | Θ(n log n) | Θ(n log n) | Θ(n log n) | Θ(1) | No | Yes |
| Counting sort | Θ(n + k) | Θ(n + k) | Θ(n + k) | Θ(n + k) | Yes | No |
| Radix sort (LSD) | Θ(d(n + b)) | Θ(d(n + b)) | Θ(d(n + b)) | Θ(n + b) | Yes | No |
| Bucket sort | Θ(n + k) | Θ(n + k)² | Θ(n²) | Θ(n + k) | Depends³ | No |
1 Average quicksort stack; it can become Θ(n) in the worst case. “In place” here allows the recursion stack.
2 With an approximately uniform distribution across k buckets and a suitable local sort.
3 Bucket sort is stable only when distribution, internal sorting and concatenation preserve equal-key order.
Parametri: n elements; k key range or bucket count; d digits; b numeric base.
Two families, two different limits
Non-comparison sorts
Counting, radix and bucket sort exploit key structure. They can be linear in n, but their cost also depends on range, digits or distribution.
Open a visualizer
Θ(n²)
Insertion sort
Inserts each element into the already sorted prefix.
Study and visualize →Θ(n log n)
Merge sort
Divides, sorts both halves, then merges them.
Study and visualize →Θ(n log n)
Quicksort
Partitions elements around a pivot.
Study and visualize →Θ(n log n)
Heapsort
Builds a max heap and repeatedly extracts the maximum.
Study and visualize →Θ(n + k)
Counting sort
Counts occurrences of each integer key.
Study and visualize →Θ(d(n + b))
Radix sort (LSD)
Sorts one digit at a time using stable passes.
Study and visualize →Θ(n + k)²
Bucket sort
Distributes values into ranges and sorts each bucket.
Study and visualize →How to choose in practice
Real libraries often use hybrids: insertion sort for small subproblems, introsort to limit quicksort’s worst case, or Timsort to exploit existing ordered runs.
Properties complexity alone does not capture
- Stable
- Equal-key elements keep their relative order. Essential for successive sorts by multiple fields.
- In place
- Uses constant or very small memory beyond the array; conventions about recursion stack must be stated.
- Adaptive
- Gets faster when the input is already partly sorted. Insertion sort is the classic example.
- Online
- Can maintain order as new elements arrive. Insertion sort supports this naturally.