Sorting¶
Sorting rearranges elements according to an ordering relation. For Java comparators, the relation must satisfy the comparator contract; arbitrary inconsistent comparisons can break sorting algorithms.
Properties¶
- Stable: equal-key elements preserve their relative input order.
- In-place: uses only a small amount of auxiliary storage under the stated convention.
- Adaptive: benefits from existing order or other input structure.
- Comparison-based: learns order only by comparing elements.
| Algorithm | Best | Average/expected | Worst | Auxiliary space | Stable |
|---|---|---|---|---|---|
| Bubble sort with early exit | Θ(n) |
Θ(n²) |
Θ(n²) |
Θ(1) |
Yes |
| Selection sort | Θ(n²) |
Θ(n²) |
Θ(n²) |
Θ(1) |
No |
| Insertion sort | Θ(n) |
Θ(n²) |
Θ(n²) |
Θ(1) |
Yes |
| Merge sort | Θ(n log n) |
Θ(n log n) |
Θ(n log n) |
Θ(n) |
Yes |
| Randomized QuickSort | Θ(n log n) |
expected Θ(n log n) |
Θ(n²) |
expected Θ(log n) stack |
No |
| Heap sort | Θ(n log n) |
Θ(n log n) |
Θ(n log n) |
Θ(1) |
No |
Comparison sorting requires Ω(n log n) comparisons in the worst case under
the decision-tree model. Counting and radix methods escape this bound by using
additional assumptions about keys.