DSA
external sort
sorting data bigger than RAM
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)
- 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