9. Partial, Online, and Adaptive Sorting

Sorting under constraints: partial sort, online insertion, adaptive merge, Timsort internals, and lazy or order-maintenance sorting.

30 items

9. Partial, online, and adaptive sorting, 30

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
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Partial Sort

Rearrange a sequence so that the smallest k elements appear in sorted order, without fully sorting the entire sequence.
algorithms sorting partial-sort selection
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Top K Sort

Extract and sort the top k elements (smallest or largest) from a sequence without fully sorting it.
algorithms sorting top-k selection
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Incremental Sort

Maintain a sorted sequence while elements are inserted one by one, updating order incrementally.
algorithms sorting incremental online
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Online Insertion Sort

Sort a sequence as elements arrive by inserting each new item into its correct position among the items already seen.
algorithms sorting online insertion-sort
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Adaptive Merge Sort

A merge sort variant that exploits existing order in the input by detecting natural runs and reducing work.
algorithms sorting adaptive merge-sort
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Natural Runs Sort

Sort a sequence by detecting already sorted runs and repeatedly merging them.
algorithms sorting adaptive merge-sort natural-runs
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Patience Sorting (LIS)

Use patience sorting to compute the length and structure of the longest increasing subsequence efficiently.
algorithms sorting lis patience-sorting
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Replacement Selection

Generate long sorted runs from a stream using a heap, commonly used in external sorting.
algorithms sorting external-memory replacement-selection
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

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.
algorithms sorting adaptive insertion-sort nearly-sorted
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

K Sorted Array Sort

Sort an array where every element is at most k positions away from its final sorted position.
algorithms sorting adaptive heap k-sorted-array
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Min Heap K Sorted Sort

Sort a k-sorted array using a sliding min heap window of size k+1.
algorithms sorting heap k-sorted-array
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Timsort Run Detection

Detect natural runs in input and normalize them for efficient merging in Timsort.
algorithms sorting timsort adaptive runs
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Galloping Merge

Accelerate merging by switching from one-by-one comparison to exponential search when one run wins repeatedly.
algorithms sorting merge timsort galloping
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Adaptive Samplesort

Partition data by sampled splitters, while adapting splitter choice to skewed or partially ordered input.
algorithms sorting samplesort adaptive partitioning
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Adaptive Shivers Sort

An adaptive merge-based sorting algorithm that merges natural runs using stack rules designed to minimize merge cost.
algorithms sorting adaptive merge-sort shivers-sort
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Patience Sort with Piles

Sort a sequence by building piles using patience sorting and then merging them.
algorithms sorting patience-sort merge piles
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Online Topological Sort

Maintain a valid topological ordering of a directed acyclic graph as vertices or edges are added over time.
algorithms sorting topological-sort online graphs
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

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.
algorithms sorting insertion-sort sentinel adaptive
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Binary Tree Online Sort

Maintain a sorted sequence by inserting elements into a binary search tree as they arrive and extracting them in order.
algorithms sorting binary-search-tree online tree-sort
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Stream Sort by Buffer

Sort a stream in bounded chunks by buffering records, sorting each chunk, and emitting sorted runs or partially ordered output.
algorithms sorting streaming buffer external-memory
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Sliding Window Sort

Maintain sorted order over a moving window of the most recent elements in a stream.
algorithms sorting streaming sliding-window online
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Rolling Median Sort

Maintain the median of a sliding window using two heaps while the window moves over a stream.
algorithms sorting median sliding-window heaps
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

External Replacement Selection

Generate long initial runs for external sorting using replacement selection with disk-based streams.
algorithms sorting external-memory replacement-selection
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Adaptive Heap Sort

A heap-based sorting method that adapts to partially ordered input to reduce unnecessary heap operations.
algorithms sorting heap-sort adaptive
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

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.
algorithms sorting smoothsort heap-sort adaptive
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Cartesian Tree Adaptive Sort

Sort by building a Cartesian tree that captures local order, then extracting elements in sorted order.
algorithms sorting cartesian-tree adaptive tree-sort
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Tournament Tree Partial Sort

Use a tournament tree to extract the smallest or largest k elements in sorted order without fully sorting the input.
algorithms sorting selection partial-sort tournament-tree
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Lazy Sort

Delay sorting work until ordered output or ordered queries are actually needed.
algorithms sorting lazy deferred adaptive
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Lazy Selection Sort

Select the next smallest element on demand, avoiding full sorting until all elements are requested.
algorithms sorting selection lazy partial-sort
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Order Maintenance Sort

Maintain a dynamically ordered sequence under insertions and comparisons without fully re-sorting.
algorithms sorting order-maintenance online data-structures