LeetCode 975: Odd Even Jump
A clear explanation of counting good starting indices using next-jump preprocessing and dynamic programming.
312 notes
A clear explanation of counting good starting indices using next-jump preprocessing and dynamic programming.
A clear explanation of returning the k closest points to the origin using squared distance and sorting.
A clear explanation of sorting an array using prefix reversals by repeatedly placing the largest remaining value.
A clear explanation of checking whether an array can be reordered into pairs where one number is double the other.
A clear explanation of checking whether words are sorted according to a custom alien alphabet order.
A clear explanation of the Hand of Straights problem using sorting, frequency counting, and greedy grouping.
A clear explanation of the Most Profit Assigning Work problem using sorting, greedy choice, and two pointers.
A clear explanation of placing even numbers at even indices and odd numbers at odd indices using two pointers.
A clear explanation of sorting an array without built-in sorting using merge sort.
A clear explanation of minimizing the array range after adding either +k or -k to every element.
A clear explanation of finding the lexicographically smallest string after queue operations using rotation and sorting.
A clear explanation of counting special-equivalent string groups by building canonical signatures from even and odd positions.
A clear explanation of summing subsequence widths by sorting and counting each element as a maximum and minimum.
A clear explanation of minimizing rescue boats using sorting, greedy choice, and two pointers.
A clear explanation of Maximum Distance in Arrays using sorted endpoints and a greedy scan.
A clear explanation of vertical tree traversal using coordinates, DFS, sorting, and column grouping.
A clear explanation of sorting squared values from a sorted array using two pointers.
A clear explanation of finding the largest valid triangle perimeter using sorting and a greedy scan.
A clear explanation of maximizing the advantage of one array over another using sorting, greedy matching, and two pointers.
A clear explanation of hiring exactly k workers with minimum total cost using wage-to-quality ratios, sorting, and a max heap.
A clear explanation of counting car fleets by sorting cars by position and tracking arrival times.
A clear explanation of solving Reveal Cards In Increasing Order using sorting and queue simulation over indices.
A clear explanation of solving Bag of Tokens using sorting, greedy choices, and two pointers.
A clear explanation of solving Minimum Increment to Make Array Unique by sorting and greedily assigning the next available value.
A clear explanation of solving Reorder Data in Log Files using custom sorting and stable handling of digit logs.
A dynamic programming solution for counting binary trees where every non-leaf node is the product of its children.
A clear explanation of rearranging a string so that selected characters follow a custom order.
A clear explanation of finding the kth smallest fraction from a sorted array using a min-heap.
A clear explanation of splitting a permutation into the maximum number of chunks using prefix maximums.
A clear explanation of splitting an array into the maximum number of chunks so sorting each chunk gives the fully sorted array.
A clear explanation of making a special binary string lexicographically largest using recursive decomposition and sorting.
A clear explanation of finding common free time by merging all employee busy intervals and returning the gaps.
A clear explanation of solving interval intersection constraints using greedy sorting and minimal point selection.
A clear explanation of finding the longest buildable word using sorting and a hash set.
A clear explanation of finding the kth smallest pair distance using sorting, binary search on the answer, and a two-pointer count.
Parse a chemical formula with nested parentheses, atom names, and multipliers using recursive descent.
Find the k most frequent words using frequency counting and custom sorting by count and lexicographical order.
A clear explanation of cutting trees in increasing height order using repeated BFS on a grid.
A greedy interval scheduling solution for finding the longest chain of valid pairs.
A counting and math solution for finding the duplicated number and the missing number in a corrupted set.
A trie-based design for returning the top three historical sentences for a typed prefix.
A greedy heap solution for taking the maximum number of courses before their deadlines.
A clear explanation of finding the largest product of three numbers using sorting or constant-space tracking.
A two-pointer guide for counting triplets that can form valid triangles after sorting the side lengths.
A clear explanation of Group Anagrams using a hash map keyed by each word's sorted character signature.
A clear explanation of Permutations II using sorting, depth-first search, and duplicate-skipping backtracking.
A SQL solution for swapping every pair of adjacent student seats while leaving the final seat unchanged when the row count is odd.
A clear geometry solution for checking whether four unordered points form a valid square.
A clear design guide for implementing an in-memory file system with directory listing, directory creation, file append, and file read operations.
A clear explanation of Array Partition using sorting and adjacent pairing to maximize the sum of pair minimums.
A clear explanation of finding the minimum difference between 24-hour clock times using minute conversion and sorting.
A clear explanation of generating minimal unique word abbreviations using grouping and trie prefixes.
A clear explanation of finding the longest dictionary word obtainable as a subsequence using two pointers and sorting rules.
A clear explanation of finding the longest uncommon subsequence among many strings using subsequence checks.
A clear explanation of assigning athlete ranks from scores using sorting while preserving original indices.
A clear explanation of maximizing capital by selecting at most k projects using sorting and a max heap.
A clear explanation of finding the minimum heater radius by sorting positions and matching each house to its nearest heater.
A clear explanation of why the median minimizes the number of moves needed to make all array elements equal.
A clear explanation of the greedy two-pointer solution for maximizing the number of content children.
A clear explanation of the greedy interval solution for finding the minimum number of arrows needed to burst all balloons.
A clear explanation of sorting characters by decreasing frequency using a hash map and sorting.
Find, for each interval, the interval with the smallest start point greater than or equal to its end point using sorting and binary search.
Remove the minimum number of intervals so the remaining intervals do not overlap, using greedy sorting by end time.
A clear explanation of finding the third distinct maximum number using one pass and constant space.
A clear explanation of reconstructing a queue using greedy sorting and indexed insertion.
A clear explanation of finding the largest subset where every pair is divisible using sorting, dynamic programming, and parent reconstruction.
A clear explanation of sorting values after applying a quadratic function using two pointers.
A clear explanation of solving Russian Doll Envelopes using sorting and longest increasing subsequence.
A clear explanation of Intersection of Two Arrays II using frequency counting.
A clear explanation of Intersection of Two Arrays using hash sets for uniqueness and fast lookup.
A clear explanation of Wiggle Sort II using sorting, median splitting, and virtual indexing.
A median-based solution for minimizing total Manhattan distance in a grid.
A greedy in-place solution for rearranging an array into a non-strict wiggle pattern.
A clear explanation of the H-Index problem using sorting, then an optimized counting approach.
A clear explanation of the 3Sum Smaller problem using sorting and the two-pointer technique.
A clear explanation of the Meeting Rooms II problem using a min heap to track active meeting end times.
A clear explanation of the Meeting Rooms problem using interval sorting to detect overlaps.
A clear explanation of detecting duplicates in an array using a hash set and sorting.
A detailed guide to solving Merge Sorted Array in-place by merging from the back with three pointers.
A clear explanation of arranging non-negative integers to form the largest possible concatenated number using a custom sort order.
A clear explanation of finding the element that appears more than half the time using Boyer-Moore voting.
A clear explanation of finding the maximum adjacent gap in sorted order using buckets and the pigeonhole principle.
Sort a singly linked list using insertion sort by splicing each node into a growing sorted list.
A clear guide to sorting an array of 0s, 1s, and 2s in place using the Dutch National Flag algorithm.
A clear guide to solving Merge Intervals by sorting intervals and merging them in one pass.
A clear explanation of finding unique combinations that sum to a target when each array element may be used at most once.
A detailed explanation of finding all unique quadruplets that sum to a target using sorting and two pointers.
A detailed explanation of finding the sum of three integers closest to a target using sorting and two pointers.
A detailed explanation of finding all unique triplets that sum to zero using sorting and two pointers.
Construct a suffix array by sorting rank pairs with radix or counting sort during the doubling method.
String sorting method that groups strings by prefixes in a trie and sorts leaf buckets for cache efficient lexicographic order.
Cache efficient string sorting algorithm that builds a trie and sorts buckets lazily for high performance on large text data.
Sort fixed width keys by processing digits from least significant to most significant using a stable inner sort.
Sort integer or string keys by processing one digit, byte, or character position at a time.
High-throughput sorting: parallel merge and quicksort, GPU bitonic and radix sort, SIMD sorting networks, and distributed partition-based sorts.
Sorting beyond main memory: external merge sort, polyphase merge, cache-oblivious techniques, LSM compaction, and database sort phases.
Sorting under constraints: partial sort, online insertion, adaptive merge, Timsort internals, and lazy or order-maintenance sorting.
Non-comparison sorts: counting, radix, and bucket sort families, string sorting, and suffix array construction.
Divide-and-conquer sorts: merge sort variants, quicksort family, heapsort, and comparison-based sorting networks.
Elementary comparison-based sorts: bubble, selection, insertion, Shell, comb, cycle, and curiosity sorts.
Searching and sorting techniques spanning sequential and parallel algorithms, from linear scan to GPU-based distribution sort.
Sort a two dimensional mesh by alternating row sorts and column sorts until the grid is globally ordered.
Sort distributed keys across hypercube processors using dimension based compare and exchange stages.
Sort data in parallel by local sorting, regular sampling, global splitter selection, redistribution, and final local merge.
Sort distributed data by assigning fixed key ranges to workers, routing records by range, then sorting locally.
Sort data across machines by sampling keys, choosing splitters, redistributing records into ordered buckets, and sorting buckets locally.
Sort very large datasets with range partitioning, distributed shuffle, and reducer local sorting.
Sort large distributed datasets by partitioning records by key range, sorting partitions locally, and writing ordered output shards.
Merge a bitonic sequence into a sorted sequence using a fixed comparator network.
Sort a fixed size sequence using a data independent network of odd even compare exchange stages.
Sort a fixed size sequence with a bitonic compare and exchange network whose schedule is independent of input values.
Sort a fixed size vector by mapping a data independent sorting network to SIMD compare, shuffle, and blend operations.
Sort small vectors using SIMD registers with a fixed bitonic compare exchange network.
Sort a block sized tile on the GPU using shared memory and cooperative threads.
Sort a small set of values inside one CUDA warp using shuffle operations and compare exchange steps.
Sort data on a GPU by selecting splitters, partitioning into buckets in parallel, then sorting buckets independently.
Sort data on a GPU by recursively merging sorted runs using parallel merge primitives.
Sort fixed width keys on a GPU using digit passes, parallel histograms, prefix sums, and scatter operations.
Sort data on a GPU using a regular bitonic compare and exchange network.
Count key frequencies in parallel, compute prefix sums, then scatter elements into sorted positions.
Sort an array by repeatedly comparing odd indexed and even indexed adjacent pairs in parallel.
Sort data by building and merging bitonic sequences through a regular compare and exchange network.
Sort integer keys by processing fixed width digit groups in parallel using counting and prefix sums.
Choose splitters from samples, partition the input into buckets, sort buckets independently, then concatenate the sorted buckets.
Partition the array around a pivot, then sort partitions concurrently using parallel recursion.
Divide the input, sort subarrays in parallel, then merge them using parallel merge procedures.
K-way merge using a tournament tree that stores winners at internal nodes and repeatedly updates the winning path.
Efficient k-way merge using a tournament tree that stores losers to reduce comparisons and improve external merge performance.
External-memory bucket sort that partitions records into ordered buckets stored on disk and sorts each bucket separately.
External-memory sorting algorithm that uses sampling to partition data into balanced buckets, then sorts each bucket independently.
External-memory radix sort that processes large datasets by distributing records into digit-based buckets across multiple passes.
External sorting algorithm that performs run generation and merging concurrently across multiple processors and disks.
Sorting method that keeps data in memory until a memory limit is reached, then spills sorted runs to external storage and merges them.
Sorting method that divides input into bounded-size chunks, sorts each chunk independently, and then combines the chunks.
External sorting method that uses memory-mapped files so large data can be accessed through virtual memory while still sorting in chunks and merging runs.
External sorting algorithm that distributes sorted runs across sequential storage tapes and repeatedly merges them.
External sorting technique that uses a heap to produce initial sorted runs longer than the available memory.
The sorting stage used before a sort-merge join when one or both inputs are not already ordered by the join key.
External sorting procedure used by database systems for ORDER BY, GROUP BY, DISTINCT, and sort-merge joins.
Sorting through hierarchical merging in Log Structured Merge Trees using compaction across levels.
Sorting method that builds a B-tree directly from sorted data using bulk loading to minimize I/O operations.
External-memory sorting method that inserts records into a buffered tree and extracts them in sorted order.
Cache oblivious sorting algorithm that achieves optimal memory transfer complexity using recursive multiway merging structures called funnels.
Sorting techniques that achieve good cache behavior without explicitly knowing cache size or block size.
Sorting techniques that explicitly use knowledge of cache size and block size to minimize memory hierarchy cost.
External-memory sorting method that partitions data into key ranges, sorts each range, and concatenates the sorted partitions.
External sorting method that merges sorted runs through staged levels so output from one level feeds the next.
External sorting algorithm that repeatedly merges groups of k sorted runs until one final sorted run remains.
External sorting algorithm that distributes sorted runs unevenly across files so repeated merges need fewer empty files and less redistribution.
External sorting algorithm that performs run generation and a single multiway merge using limited memory.
Sort data that does not fit in memory by dividing it into sorted runs and merging them using external storage.
Maintain a dynamically ordered sequence under insertions and comparisons without fully re-sorting.
Select the next smallest element on demand, avoiding full sorting until all elements are requested.
Delay sorting work until ordered output or ordered queries are actually needed.
Use a tournament tree to extract the smallest or largest k elements in sorted order without fully sorting the input.
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.
Generate long initial runs for external sorting using replacement selection with disk-based streams.
Maintain the median of a sliding window using two heaps while the window moves over a stream.
Maintain sorted order over a moving window of the most recent elements in a stream.
Sort a stream in bounded chunks by buffering records, sorting each chunk, and emitting sorted runs or partially ordered output.
Maintain a sorted sequence by inserting elements into a binary search tree as they arrive and extracting them in order.
Optimize insertion sort by placing the minimum element at the front so the inner loop does not need a bounds check.
Maintain a valid topological ordering of a directed acyclic graph as vertices or edges are added over time.
Sort a sequence by building piles using patience sorting and then merging them.
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.
Accelerate merging by switching from one-by-one comparison to exponential search when one run wins repeatedly.
Detect natural runs in input and normalize them for efficient merging in Timsort.
Sort a k-sorted array using a sliding min heap window of size k+1.
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.
Generate long sorted runs from a stream using a heap, commonly used in external sorting.
Use patience sorting to compute the length and structure of the longest increasing subsequence efficiently.
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.
Sort a sequence as elements arrive by inserting each new item into its correct position among the items already seen.
Maintain a sorted sequence while elements are inserted one by one, updating order incrementally.
Extract and sort the top k elements (smallest or largest) from a sequence without fully sorting it.
Rearrange a sequence so that the smallest k elements appear in sorted order, without fully sorting the entire sequence.
Radix sort for signed integers by transforming values to preserve ordering across negative and positive ranges.
Radix sort for floating-point numbers by transforming their bit representation to preserve numeric order.
Difference cover modulo 7 suffix array construction method that generalizes DC3 with a larger recursive sample.
Difference cover modulo 3 algorithm for linear-time suffix array construction using radix sorting and merging.
Linear-time suffix array construction using the DC3 algorithm that recursively sorts positions modulo 3.
Linear-time suffix array construction algorithm based on induced sorting of LMS suffixes.
Linear-time technique for suffix array construction that induces order of suffixes from a subset of sorted suffixes.
LSD radix sort variant that processes keys byte by byte from least significant to most significant.
Radix sort that processes fixed-width keys one byte at a time using 256 counting buckets.
Radix sort specialized for fixed-width machine words using byte or bit extraction for high throughput.
Counting sort variant that stores counts only for keys that appear, avoiding dense arrays over large key ranges.
Sort values by mapping them to a dense rank space and ordering by compressed indices.
Extend counting sort to handle negative integers by shifting keys into a nonnegative index range.
Construct a suffix array by iteratively sorting suffixes using doubling technique with rank pairs.
String sorting algorithm that uses three-way partitioning on characters to efficiently handle repeated prefixes.
String sorting algorithm that partitions strings by the character at the current depth using three-way quicksort.
In-place MSD radix string sort that partitions strings by character using American flag style bucket permutation.
MSD radix sort variant that partitions keys by the most significant byte and recursively sorts subarrays.
Sample sort specialized for integer keys using range-based partitioning and optional radix-style bucket classification.
In-place parallel super scalar samplesort for high performance comparison sorting on modern multicore machines.
High performance radix sort variant using cache friendly block partitioning and branchless techniques.
In place binary radix sort that partitions keys by bits from most significant to least significant.
Hybrid distribution and comparison sort that adapts between radix-like partitioning and comparison sorting.
Distribution sorting algorithm that approximates uniform distribution and then refines with insertion sort.
Sort integer keys by placing each value into a direct address slot over a small contiguous range.
Sort elements by building a frequency histogram and reconstructing the output from cumulative counts.
Bucket sort variant that assumes uniform distribution and uses equal-width buckets with simple mapping.
Distribute elements into buckets based on value ranges and sort each bucket independently.
Sort integers by processing bits directly using partitioning instead of counting arrays.
Sort integers by counting occurrences of each key and reconstructing the output in linear time.
Sort digit based keys by redistributing elements inside the original array with only small auxiliary bucket state.
In place radix sort that partitions elements by digit using cycle leader permutation.
Sort keys by processing the most significant digit first and recursively sorting subarrays.
Counting-based stable sorting technique that maps keys to index ranges using frequency and prefix sums.
Stable variant of counting sort using prefix sums to preserve relative order of equal keys.
Merge-based sorting algorithm that uses a tournament tree to repeatedly select the next smallest element.
Merge sort variant that merges more than two sorted sequences at each step.
Divide and conquer sorting algorithm that uses sampling to partition data into balanced buckets.
Merge sort variant that improves locality without tuning parameters for a specific cache size.
Merge sort variant designed to improve cache locality by structuring recursion and merging to fit memory hierarchies.
Sorting network algorithm based on recursively sorting halves and merging them with Batcher's odd even merge network.
Sorting network that sorts by repeatedly applying pairwise compare and swap stages.
Sorting network algorithm that recursively merges sorted sequences using odd even comparisons.
Comparison sorting algorithm that sorts a bitonic sequence using structured compare and swap operations.
Comparison optimal sorting algorithm that minimizes comparisons using a structured insertion schedule.
Comparison-optimal sorting algorithm that combines merging and insertion guided by a structured schedule.
Heapsort variant based on weak heaps, reducing the number of comparisons while retaining in-place sorting.
Heapsort variant that uses a ternary heap with three children per node.
Heapsort variant that uses bottom up sift down to reduce comparisons during heapify.
Comparison sorting algorithm that builds a heap and repeatedly extracts the maximum.
Quicksort variant using the Lomuto single-index partition scheme.
Quicksort variant that uses Hoare's two pointer partition scheme.
Quicksort variant that selects the pivot using Tukey's ninther, the median of three medians of three.
Quicksort variant that chooses the pivot as the median of the first, middle, and last elements.
Quicksort variant that preserves the relative order of equal elements.
Quicksort variant that processes elements in blocks to reduce branch misprediction and improve cache efficiency.
Quicksort variant that detects and avoids bad input patterns using adaptive partitioning and pivot selection.
Hybrid sorting algorithm that starts with quicksort and falls back to heapsort when recursion becomes too deep.
Quicksort variant that partitions the array using two pivots into three regions.
Quicksort variant that partitions into less than, equal to, and greater than pivot.
Quicksort variant that selects pivots randomly to avoid worst case patterns.
Divide and conquer sorting algorithm that partitions the array around a pivot and recursively sorts both sides.
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.
Stable merge sort variant that uses block rearrangement and a small buffer to reduce auxiliary memory.
Merge sort variant that reduces auxiliary memory by merging sorted ranges inside the original array.
Adaptive merge sort that detects existing sorted runs and merges them.
Iterative merge sort that builds sorted runs from size 1 upward without recursion.
Recursive merge sort that splits the array from the top and merges sorted halves.
Divide and conquer sorting algorithm that splits the array, sorts recursively, and merges in linear time.
A simple quadratic sorting algorithm that compares all pairs and swaps out-of-order elements.
Repeatedly place all occurrences of the current minimum value before moving to the next distinct value.
Sort by building a Cartesian tree and extracting elements via inorder traversal.
A variant of heapsort using weak heaps with fewer comparisons.
An adaptive in-place comparison sort based on Leonardo heaps.
Sort by repeatedly selecting the minimum element using a tournament tree.
Insert all elements into a binary search tree, then traverse the tree in sorted order.
Sort by building piles using patience card game rules and then merging them.
An insertion-based sorting algorithm that leaves gaps between elements to reduce shifting.
Extract increasing subsequences and merge them to form a sorted sequence.
Sort non-negative integers by simulating gravity on beads arranged in columns.
A deliberately inefficient recursive sorting algorithm based on divide and conquer followed by maximum placement.
A recursive sorting algorithm with extremely poor performance based on overlapping subproblems.
Sort by repeatedly flipping prefixes to move the maximum element to its correct position.
Minimizes writes by placing each element directly into its correct position using cycles.
A bubble-sort variant that compares elements at a shrinking gap to remove long-distance inversions early.
Shell sort using Sedgewick gap sequence for improved practical performance.
Shell sort using Hibbard gap sequence 1, 3, 7, 15, ..., improving over simple halving.
Shell sort using the original gap sequence n/2, n/4, ..., 1.
Generalization of insertion sort that compares elements at a gap, reducing long-distance inversions early.
Insertion sort that uses binary search to find the insertion position, reducing comparisons.
Build a sorted sequence by inserting each element into its correct position.
Select both minimum and maximum elements in each pass and place them at the beginning and end.
A stable variant of selection sort that preserves the relative order of equal elements by shifting instead of swapping.
Repeatedly select the minimum element from the unsorted portion and place it at the beginning.
A simple sorting algorithm that moves elements backward when out of order, similar to insertion sort with swaps.
A variation of bubble sort that alternates between comparing odd-even and even-odd index pairs.
Repeatedly swap adjacent elements that are out of order until the sequence becomes sorted.
A bidirectional variant of bubble sort that alternates passes from left to right and right to left.
Bubble sort with early termination when no swaps occur, reducing unnecessary passes on nearly sorted data.
Linear time suffix array construction using induced sorting of LMS substrings.
Generalized divide and conquer suffix array construction using modulo 7 partitioning.
Linear time suffix array construction using the DC3 divide and conquer strategy.
Build a suffix array using the prefix doubling technique with iterative ranking.
Select the appropriate sorting algorithm based on input size, data characteristics, memory constraints, and required guarantees such as stability or worst-case bounds.
Identify boundary errors, broken invariants, and comparator mistakes that cause sorting implementations to fail on edge cases or duplicate-heavy inputs.
Verify both the ordering and permutation properties of sorting implementations using randomized, edge-case, and adversarial test strategies.
Distribute sorting work across multiple processors to reduce wall-clock time, with analysis of total work, span, communication, and synchronization.
Prove that any comparison-based sorting algorithm requires Ω(n log n) comparisons in the worst case using a decision tree argument.
Count pairs of elements in the wrong relative order to measure how far an array is from sorted, using a modified merge sort in O(n log n) time.
Replace large or sparse keys with small dense ranks that preserve order, making range-based and indexed structures practical on wide-valued data.
Sort structured values by one or more fields while moving the full record, with attention to key extraction, stability, and multi-key ordering.
Define correct comparison relations for user-defined types and non-trivial orderings — consistency requirements that sorting correctness depends on.
Exploit near-sorted structure in inputs like append-only logs or incremental updates to sort in linear or near-linear time.
Sort datasets that exceed main memory by organizing the algorithm around sequential disk access, merge passes, and minimizing I/O operations.
Find the middle value of a collection in linear time using selection algorithms, without the overhead of a full sort.
Find the element at a given rank using quicksort's partition step but recursing into only one side, achieving expected linear time.
Find the largest or smallest k elements without sorting the full input, using a heap or partition-based approach.
Produce only the smallest k elements in sorted order rather than sorting the entire array, reducing unnecessary work when the full order is not needed.
A stable sort preserves the original relative order of equal keys — an extra guarantee required when sorting by secondary fields or compound criteria.
Distribute elements into buckets by value range, sort each bucket, then concatenate — achieving linear expected time on uniformly distributed input.
Sort keys digit by digit using a stable subroutine, achieving linear time for fixed-width integers without any key comparisons.
Sort integer keys from a small range in linear time by counting occurrences and reconstructing the output from those counts.
Build a max-heap in place, then repeatedly extract the maximum to produce a sorted array in O(n log n) worst-case time.
Partition around a pivot so smaller elements go left and larger go right, then recursively sort each partition in expected O(n log n) time.
Divide the input into halves, recursively sort each half, then merge them — combining local order into global order in O(n log n) time.
Build a sorted prefix one element at a time by inserting each new element into its correct position within the already-sorted portion.
Sort by repeatedly selecting the minimum element from the unsorted suffix and placing it into the next output position.
A sorting algorithm is correct only when its output is both ordered and a permutation of the input — two properties every implementation must preserve.
Merging combines two sorted singly linked lists into one sorted list by relinking nodes.
Sorting algorithms from fundamental contracts through comparison-based, linear-time, and specialized variants, with selection, external sorting, and correctness analysis.