# Sorting Algorithms
## Algorithms — The Codex Coding
**URL:** https://thecodex.expert/coding/algorithms/sorting/
**Type:** algorithm | **Confidence:** high | **Last verified:** 2026-06-01

## CANONICAL DEFINITION
Sorting algorithms arrange a sequence of elements into a defined order. Comparison sorts are provably bounded below by Omega(n log n) comparisons in the worst case. Non-comparison sorts (counting, radix, bucket) can achieve O(n) by exploiting the structure of the keys.

## COMPLEXITY
- comparison_lower_bound: Omega(n log n)
- merge_sort_all_cases: Theta(n log n)
- quicksort_average: Theta(n log n)
- quicksort_worst: Theta(n^2)
- counting_sort: O(n+k)

## REQUIRES
algorithms/complexity, data-structures/arrays

## ENABLES
algorithms/sorting/merge-sort, algorithms/sorting/quicksort

## COMMONLY CONFUSED WITH
best case != overall quality; in-place != O(1) space (quicksort uses O(log n) stack); stable != correct

## SOURCES
- CLRS 4th ed. §8.1 (lower bound proof)
- Peters 2002 Timsort
- Knuth TAOCP Vol.3 §5
- Sedgewick & Wayne Algorithms 4th ed. Ch.2

*The Codex Coding — thecodex.expert/coding/ — Free forever — Mumbai, India*