9. Partial, Online, and Adaptive Sorting
Sorting under constraints: partial sort, online insertion, adaptive merge, Timsort internals, and lazy or order-maintenance sorting.
18 notes
Sorting under constraints: partial sort, online insertion, adaptive merge, Timsort internals, and lazy or order-maintenance sorting.
Delay sorting work until ordered output or ordered queries are actually needed.
Sort by building a Cartesian tree that captures local order, then extracting elements in sorted order.
Sort in place with a heap-like structure that keeps worst-case O(n log n) time while approaching linear time on nearly sorted input.
A heap-based sorting method that adapts to partially ordered input to reduce unnecessary heap operations.
Optimize insertion sort by placing the minimum element at the front so the inner loop does not need a bounds check.
An adaptive merge-based sorting algorithm that merges natural runs using stack rules designed to minimize merge cost.
Partition data by sampled splitters, while adapting splitter choice to skewed or partially ordered input.
Detect natural runs in input and normalize them for efficient merging in Timsort.
Sort an array where every element is at most k positions away from its final sorted position.
Sort an almost ordered sequence efficiently by using insertion sort, whose running time improves when few elements are far from their final positions.
Sort a sequence by detecting already sorted runs and repeatedly merging them.
A merge sort variant that exploits existing order in the input by detecting natural runs and reducing work.
Stable adaptive merge sort that uses power based ordering of runs for near optimal merging.
Adaptive stable sorting algorithm that combines merge sort with run detection and insertion sort.
Adaptive merge sort that detects existing sorted runs and merges them.
An adaptive in-place comparison sort based on Leonardo heaps.
Exploit near-sorted structure in inputs like append-only logs or incremental updates to sort in linear or near-linear time.