DSA
stable sort
preserves order of equal keys
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)
- the O(n log n) wallinfo-theoretic lower bound for comparison sorts
- Timsort/introsortthe real-world hybrids