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