tag

#adaptive

18 pages tagged

Wiki › Algorithms › 01. Searching and Sorting ›

9. Partial, Online, and Adaptive Sorting

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...
algorithms sorting adaptive online May 6, 2026
Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.16 Nearly Sorted Data

6.16 Nearly Sorted Data Nearly sorted inputs appear frequently in practice. Logs appended over time, incremental updates, and cached results often differ only slightly from sorted order. Algorithms that exploit this structure can run in linear or near-linear time. Problem You have an array A[0..n-1] that is close to sorted. You want to sort it faster than general-purpose O(n log n) algorithms. Measuring “Nearly Sorted” Several measures capture how far...
algorithms sorting adaptive nearly-sorted May 4, 2026
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Natural Merge Sort

Natural Merge Sort Natural merge sort improves merge sort by exploiting existing order in the input. Instead of splitting blindly, it scans the array to find already sorted runs, then merges those runs. This approach adapts to partially sorted data and can reduce the number of passes. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots \le A[n-1] $$ Idea A...
algorithms sorting merge-sort adaptive
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Cartesian Tree Adaptive Sort

Cartesian Tree Adaptive Sort Cartesian tree adaptive sort builds a Cartesian tree from the input sequence and uses its structure to produce sorted output. The tree encodes both the order of elements and their relative values. You use it when input has structure that can be exploited through tree shape. Problem Given an array ( A ), sort it by: constructing a Cartesian tree extracting elements in sorted order A...
algorithms sorting cartesian-tree adaptive tree-sort
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Adaptive Shivers Sort

Adaptive Shivers Sort Adaptive Shivers sort is a run-based merge sort that improves how runs are merged. It detects natural runs and applies a stack discipline with carefully chosen merge rules to keep merges balanced. You use it when input contains natural runs and you want tighter control over merge cost than simple strategies. Problem Given an array ( A ), sort it by: detecting natural runs merging them in...
algorithms sorting adaptive merge-sort shivers-sort
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Smoothsort Adaptive Heap Sort

Smoothsort Adaptive Heap Sort Smoothsort is an adaptive heap-based sorting algorithm. It preserves the in-place and worst-case guarantees of heapsort, but it performs much less work when the input is already close to sorted. You use it when constant extra space matters and the input may contain existing order. Problem Given an array ( A ) of length ( n ), sort it in place while taking advantage of nearly...
algorithms sorting smoothsort heap-sort adaptive
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Insertion Sort with Sentinel

Insertion Sort with Sentinel Insertion sort with sentinel is a small optimization of insertion sort. It first places the minimum element at the beginning of the array. That element acts as a sentinel, so the inner loop can stop without checking whether it has reached the start of the array. You use it when implementing insertion sort as a low-level routine, especially inside hybrid sorts. Problem Given an array (...
algorithms sorting insertion-sort sentinel adaptive
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Adaptive Heap Sort

Adaptive Heap Sort Adaptive heap sort modifies standard heapsort to take advantage of existing order in the input. While classical heapsort treats all inputs the same, adaptive variants reduce work when the input is already partially sorted. You use it when you want heap-based guarantees with some sensitivity to input structure. Problem Given an array ( A ), sort it while: preserving ( O(n \log n) ) worst-case bounds reducing...
algorithms sorting heap-sort adaptive
Wiki › Algorithms › 01. Searching and Sorting › 6. Elementary Sorting ›

Smoothsort

Smoothsort Smoothsort is an adaptive comparison-based sorting algorithm designed by Edsger Dijkstra. It is related to heapsort, but it uses a forest of Leonardo heaps instead of one binary heap. The main advantage is adaptivity. Smoothsort runs in linear time on already sorted or nearly sorted data, while preserving the same worst-case bound as heapsort. Problem Given a sequence $A$ of length $n$, reorder it such that $$ A[0] \le...
algorithms sorting smoothsort heap-sort adaptive
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Timsort Run Detection

Timsort Run Detection Timsort run detection is the first phase of Timsort. It scans the array, detects natural runs, and normalizes them into a form suitable for efficient merging. You use it as part of adaptive sorting where exploiting existing order matters. Problem Given an array ( A ), partition it into runs such that: each run is monotonic (non-decreasing or strictly decreasing) runs satisfy a minimum length constraint Idea...
algorithms sorting timsort adaptive runs
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

K Sorted Array Sort

K Sorted Array Sort K sorted array sort handles a nearly sorted array where every element is at most ( k ) positions away from its final sorted position. This stronger assumption allows a heap based method faster than general sorting. You use it when the disorder is locally bounded. Problem Given an array ( A ) of length ( n ), where each element is at most ( k...
algorithms sorting adaptive heap k-sorted-array
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Lazy Sort

Lazy Sort Lazy sort delays sorting until the program needs ordered output. Instead of immediately sorting every inserted element, it stores unsorted data and performs sorting only when a query requires order. You use it when many updates happen before few sorted reads. Problem Maintain a collection that supports: inserting elements requesting sorted output avoiding unnecessary sorting work when sorted output is never requested Idea Keep inserted elements in an...
algorithms sorting lazy deferred adaptive
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Adaptive Merge Sort

Adaptive Merge Sort Adaptive merge sort improves standard merge sort by detecting existing order in the input. Instead of blindly splitting into fixed halves, it identifies already sorted subsequences called runs and merges them. You use it when the input often contains partial order. Problem Given an array ( A ) of size ( n ), sort it while taking advantage of any existing sorted segments. Idea If the array...
algorithms sorting adaptive merge-sort
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Timsort

Timsort Timsort is a hybrid stable sorting algorithm designed for real world data. It combines ideas from merge sort and insertion sort, with strong emphasis on exploiting existing order. It is the default sorting algorithm in languages such as Python and Java (for objects). Its design focuses on practical performance rather than purely theoretical bounds. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le...
algorithms sorting timsort adaptive
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Natural Runs Sort

Natural Runs Sort Natural runs sort is an adaptive sorting method that first finds sorted subsequences already present in the input. These subsequences are called natural runs. The algorithm then merges the runs until the whole sequence is sorted. You use it when input data often contains long ordered stretches. Problem Given an array ( A ) of size ( n ), sort it by exploiting existing non-decreasing regions. A...
algorithms sorting adaptive merge-sort natural-runs
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Powersort

Powersort Powersort is a stable adaptive merge sort that improves how runs are merged. It builds on the same idea as Timsort, detecting natural runs in the input, but uses a principled method to decide merge order based on a notion of power derived from positions in the array. The goal is to achieve near optimal merge trees with low overhead. Problem Given an array $A$ of length $n$, reorder...
algorithms sorting powersort adaptive
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Adaptive Samplesort

Adaptive Samplesort Adaptive samplesort is a samplesort variant that chooses splitters from the input and adjusts partitioning to the observed distribution. It is useful when the input has skew, duplicates, or uneven key ranges. You use it when ordinary quicksort or fixed bucket sorting may create badly imbalanced partitions. Problem Given an array ( A ) of length ( n ), sort it by dividing values into buckets whose boundaries...
algorithms sorting samplesort adaptive partitioning
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Nearly Sorted Insertion Sort

Nearly Sorted Insertion Sort Nearly sorted insertion sort is ordinary insertion sort applied to input that is already close to sorted order. Insertion sort adapts well to this case because each element moves only a short distance. You use it when the input has small disorder, such as data produced by appending a few new records, merging mostly ordered logs, or correcting a sequence after minor edits. Problem Given an...
algorithms sorting adaptive insertion-sort nearly-sorted