DSA
the O(n log n) wall
info-theoretic lower bound for comparison sorts
Source board
This definition comes from the board below. Open it to see the term in context.
Sorting and SearchingDSAMore terms from this board
- binary searchhalve a SORTED range → O(log n)
- binary-search-on-the-answersearch a monotonic predicate (optimization)
- comparison sortorders by comparing pairs (≥ n log n)
- counting/radix/bucketnon-comparison sorts (integer keys, beat the wall)
- external sortsorting data bigger than RAM
- heapsortrepeated extract-max (in-place)
- invariantthe loop condition that keeps the answer in range (off-by-one killer)
- merge sortsplit/sort/merge (stable, O(n) space)
- pivot/partitionquicksort's split step
- quicksortpivot + partition (in-place, O(n²) worst)
- stable sortpreserves order of equal keys
- Timsort/introsortthe real-world hybrids