Sorting under constraints: partial sort, online insertion, adaptive merge, Timsort internals, and lazy or order-maintenance sorting.
| index | slug | name |
|---|---|---|
| 256 | partial-sort | Partial Sort |
| 257 | top-k-sort | Top K Sort |
| 258 | incremental-sort | Incremental Sort |
| 259 | online-insertion-sort | Online Insertion Sort |
| 260 | adaptive-merge-sort | Adaptive Merge Sort |
| 261 | natural-runs-sort | Natural Runs Sort |
| 262 | patience-sorting-lis | Patience Sorting for LIS |
| 263 | replacement-selection | Replacement Selection |
| 264 | nearly-sorted-insertion-sort | Nearly Sorted Insertion Sort |
| 265 | k-sorted-array-sort | K Sorted Array Sort |
| 266 | min-heap-k-sorted-sort | Min Heap K Sorted Sort |
| 267 | timsort-run-detection | Timsort Run Detection |
| 268 | galloping-merge | Galloping Merge |
| 269 | adaptive-samplesort | Adaptive Samplesort |
| 270 | adaptive-shivers-sort | Adaptive Shivers Sort |
| 271 | patience-sort-with-piles | Patience Sort with Piles |
| 272 | online-topological-sort | Online Topological Sort |
| 273 | insertion-sort-with-sentinel | Insertion Sort with Sentinel |
| 274 | binary-tree-online-sort | Binary Tree Online Sort |
| 275 | stream-sort-by-buffer | Stream Sort by Buffer |
| 276 | sliding-window-sort | Sliding Window Sort |
| 277 | rolling-median-sort | Rolling Median Sort |
| 278 | external-replacement-selection | External Replacement Selection |
| 279 | adaptive-heap-sort | Adaptive Heap Sort |
| 280 | smoothsort-adaptive-heap-sort | Smoothsort Adaptive Heap Sort |
| 281 | cartesian-tree-adaptive-sort | Cartesian Tree Adaptive Sort |
| 282 | tournament-tree-partial-sort | Tournament Tree Partial Sort |
| 283 | lazy-sort | Lazy Sort |
| 284 | lazy-selection-sort | Lazy Selection Sort |
| 285 | order-maintenance-sort | Order Maintenance Sort |
Partial SortRearrange a sequence so that the smallest k elements appear in sorted order, without fully sorting the entire sequence.
Top K SortExtract and sort the top k elements (smallest or largest) from a sequence without fully sorting it.
Incremental SortMaintain a sorted sequence while elements are inserted one by one, updating order incrementally.
Online Insertion SortSort a sequence as elements arrive by inserting each new item into its correct position among the items already seen.
Adaptive Merge SortA merge sort variant that exploits existing order in the input by detecting natural runs and reducing work.
Natural Runs SortSort a sequence by detecting already sorted runs and repeatedly merging them.
Patience Sorting (LIS)Use patience sorting to compute the length and structure of the longest increasing subsequence efficiently.
Replacement SelectionGenerate long sorted runs from a stream using a heap, commonly used in external sorting.
Nearly Sorted Insertion SortSort an almost ordered sequence efficiently by using insertion sort, whose running time improves when few elements are far from their final positions.
K Sorted Array SortSort an array where every element is at most k positions away from its final sorted position.
Min Heap K Sorted SortSort a k-sorted array using a sliding min heap window of size k+1.
Timsort Run DetectionDetect natural runs in input and normalize them for efficient merging in Timsort.
Galloping MergeAccelerate merging by switching from one-by-one comparison to exponential search when one run wins repeatedly.
Adaptive SamplesortPartition data by sampled splitters, while adapting splitter choice to skewed or partially ordered input.
Adaptive Shivers SortAn adaptive merge-based sorting algorithm that merges natural runs using stack rules designed to minimize merge cost.
Patience Sort with PilesSort a sequence by building piles using patience sorting and then merging them.
Online Topological SortMaintain a valid topological ordering of a directed acyclic graph as vertices or edges are added over time.
Insertion Sort with SentinelOptimize insertion sort by placing the minimum element at the front so the inner loop does not need a bounds check.
Binary Tree Online SortMaintain a sorted sequence by inserting elements into a binary search tree as they arrive and extracting them in order.
Stream Sort by BufferSort a stream in bounded chunks by buffering records, sorting each chunk, and emitting sorted runs or partially ordered output.
Sliding Window SortMaintain sorted order over a moving window of the most recent elements in a stream.
Rolling Median SortMaintain the median of a sliding window using two heaps while the window moves over a stream.
External Replacement SelectionGenerate long initial runs for external sorting using replacement selection with disk-based streams.
Adaptive Heap SortA heap-based sorting method that adapts to partially ordered input to reduce unnecessary heap operations.
Smoothsort Adaptive Heap SortSort in place with a heap-like structure that keeps worst-case O(n log n) time while approaching linear time on nearly sorted input.
Cartesian Tree Adaptive SortSort by building a Cartesian tree that captures local order, then extracting elements in sorted order.
Tournament Tree Partial SortUse a tournament tree to extract the smallest or largest k elements in sorted order without fully sorting the input.
Lazy SortDelay sorting work until ordered output or ordered queries are actually needed.
Lazy Selection SortSelect the next smallest element on demand, avoiding full sorting until all elements are requested.
Order Maintenance SortMaintain a dynamically ordered sequence under insertions and comparisons without fully re-sorting.