DSA
counting/radix/bucket
non-comparison sorts (integer keys, beat the wall)
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)
- 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
- the O(n log n) wallinfo-theoretic lower bound for comparison sorts
- Timsort/introsortthe real-world hybrids