LeetCode 1099: Two Sum Less Than K
A clear explanation of finding the maximum sum of two numbers less than k using a two-pointer approach on a sorted array.
Tag
Sorting
325 notes
LeetCode 1094: Car Pooling
A clear explanation of determining if a car can transport all passengers using a difference array for passenger count tracking.
LeetCode 1090: Largest Values From Labels
A clear explanation of selecting the maximum sum subset under item and label count constraints using a greedy approach.
LeetCode 1086: High Five
A clear explanation of computing each student's top-5 average score using sorting and grouping.
LeetCode 1065: Index Pairs of a String
A clear explanation of finding all index pairs where a word from the list appears in a text string using a trie.
LeetCode 1058: Minimize Rounding Error to Meet Target
A clear explanation of minimizing total rounding error when rounding prices to meet a target sum using a greedy approach.
LeetCode 1057: Campus Bikes
A clear explanation of greedily assigning bikes to workers based on Manhattan distance, prioritizing by distance then worker then bike index.
LeetCode 1054: Distant Barcodes
A clear explanation of rearranging barcodes so no two adjacent barcodes are equal using a greedy max-heap approach.
LeetCode 1051: Height Checker
A clear explanation of counting students not in the expected height order by comparing the array to its sorted version.
LeetCode 1040: Moving Stones Until Consecutive II
A clear explanation of finding minimum and maximum moves to make stones consecutive using a sliding window.
LeetCode 1030: Matrix Cells in Distance Order
A clear explanation of sorting matrix cells by Chebyshev distance from a given center cell using BFS.
LeetCode 1029: Two City Scheduling
A clear explanation of minimizing total travel cost for two-city scheduling using a greedy refund approach after sending everyone to city A.
LeetCode 1005: Maximize Sum Of Array After K Negations
A clear explanation of maximizing array sum after exactly k negations using a greedy strategy.
LeetCode 954: Array of Doubled Pairs
A clear explanation of checking whether an array can be reordered into pairs where one number is double the other.
LeetCode 953: Verifying an Alien Dictionary
A clear explanation of checking whether words are sorted according to a custom alien alphabet order.
LeetCode 910: Smallest Range II
A clear explanation of minimizing the array range after adding either +k or -k to every element.
LeetCode 720: Longest Word in Dictionary
A clear explanation of finding the longest buildable word using sorting and a hash set.
LeetCode 692: Top K Frequent Words
Find the k most frequent words using frequency counting and custom sorting by count and lexicographical order.
LeetCode 524: Longest Word in Dictionary through Deleting
A clear explanation of finding the longest dictionary word obtainable as a subsequence using two pointers and sorting rules.
LeetCode 324: Wiggle Sort II
A clear explanation of Wiggle Sort II using sorting, median splitting, and virtual indexing.
LeetCode 259: 3Sum Smaller
A clear explanation of the 3Sum Smaller problem using sorting and the two-pointer technique.
LeetCode 217: Contains Duplicate
A clear explanation of detecting duplicates in an array using a hash set and sorting.
LeetCode 975: Odd Even Jump
A clear explanation of counting good starting indices using next-jump preprocessing and dynamic programming.
LeetCode 973: K Closest Points to Origin
A clear explanation of returning the k closest points to the origin using squared distance and sorting.
LeetCode 969: Pancake Sorting
A clear explanation of sorting an array using prefix reversals by repeatedly placing the largest remaining value.
LeetCode 846: Hand of Straights
A clear explanation of the Hand of Straights problem using sorting, frequency counting, and greedy grouping.
LeetCode 826: Most Profit Assigning Work
A clear explanation of the Most Profit Assigning Work problem using sorting, greedy choice, and two pointers.
LeetCode 922: Sort Array By Parity II
A clear explanation of placing even numbers at even indices and odd numbers at odd indices using two pointers.
LeetCode 912: Sort an Array
A clear explanation of sorting an array without built-in sorting using merge sort.
LeetCode 899: Orderly Queue
A clear explanation of finding the lexicographically smallest string after queue operations using rotation and sorting.
LeetCode 893: Groups of Special-Equivalent Strings
A clear explanation of counting special-equivalent string groups by building canonical signatures from even and odd positions.
LeetCode 891: Sum of Subsequence Widths
A clear explanation of summing subsequence widths by sorting and counting each element as a maximum and minimum.
LeetCode 881: Boats to Save People
A clear explanation of minimizing rescue boats using sorting, greedy choice, and two pointers.
LeetCode 624: Maximum Distance in Arrays
A clear explanation of Maximum Distance in Arrays using sorted endpoints and a greedy scan.
LeetCode 987: Vertical Order Traversal of a Binary Tree
A clear explanation of vertical tree traversal using coordinates, DFS, sorting, and column grouping.
LeetCode 977: Squares of a Sorted Array
A clear explanation of sorting squared values from a sorted array using two pointers.
LeetCode 976: Largest Perimeter Triangle
A clear explanation of finding the largest valid triangle perimeter using sorting and a greedy scan.
LeetCode 870: Advantage Shuffle
A clear explanation of maximizing the advantage of one array over another using sorting, greedy matching, and two pointers.
LeetCode 857: Minimum Cost to Hire K Workers
A clear explanation of hiring exactly k workers with minimum total cost using wage-to-quality ratios, sorting, and a max heap.
LeetCode 853: Car Fleet
A clear explanation of counting car fleets by sorting cars by position and tracking arrival times.
LeetCode 950: Reveal Cards In Increasing Order
A clear explanation of solving Reveal Cards In Increasing Order using sorting and queue simulation over indices.
LeetCode 948: Bag of Tokens
A clear explanation of solving Bag of Tokens using sorting, greedy choices, and two pointers.
LeetCode 945: Minimum Increment to Make Array Unique
A clear explanation of solving Minimum Increment to Make Array Unique by sorting and greedily assigning the next available value.
LeetCode 937: Reorder Data in Log Files
A clear explanation of solving Reorder Data in Log Files using custom sorting and stable handling of digit logs.
LeetCode 823: Binary Trees With Factors
A dynamic programming solution for counting binary trees where every non-leaf node is the product of its children.
LeetCode 791: Custom Sort String
A clear explanation of rearranging a string so that selected characters follow a custom order.
LeetCode 786: K-th Smallest Prime Fraction
A clear explanation of finding the kth smallest fraction from a sorted array using a min-heap.
LeetCode 769: Max Chunks To Make Sorted
A clear explanation of splitting a permutation into the maximum number of chunks using prefix maximums.
LeetCode 768: Max Chunks To Make Sorted II
A clear explanation of splitting an array into the maximum number of chunks so sorting each chunk gives the fully sorted array.
LeetCode 761: Special Binary String
A clear explanation of making a special binary string lexicographically largest using recursive decomposition and sorting.
LeetCode 759: Employee Free Time
A clear explanation of finding common free time by merging all employee busy intervals and returning the gaps.
LeetCode 757: Set Intersection Size At Least Two
A clear explanation of solving interval intersection constraints using greedy sorting and minimal point selection.
LeetCode 719: Find K-th Smallest Pair Distance
A clear explanation of finding the kth smallest pair distance using sorting, binary search on the answer, and a two-pointer count.
LeetCode 726: Number of Atoms
Parse a chemical formula with nested parentheses, atom names, and multipliers using recursive descent.
LeetCode 675: Cut Off Trees for Golf Event
A clear explanation of cutting trees in increasing height order using repeated BFS on a grid.
LeetCode 646: Maximum Length of Pair Chain
A greedy interval scheduling solution for finding the longest chain of valid pairs.
LeetCode 645: Set Mismatch
A counting and math solution for finding the duplicated number and the missing number in a corrupted set.
LeetCode 642: Design Search Autocomplete System
A trie-based design for returning the top three historical sentences for a typed prefix.
LeetCode 630: Course Schedule III
A greedy heap solution for taking the maximum number of courses before their deadlines.
LeetCode 628: Maximum Product of Three Numbers
A clear explanation of finding the largest product of three numbers using sorting or constant-space tracking.
LeetCode 611: Valid Triangle Number
A two-pointer guide for counting triplets that can form valid triangles after sorting the side lengths.
LeetCode 49: Group Anagrams
A clear explanation of Group Anagrams using a hash map keyed by each word's sorted character signature.
LeetCode 47: Permutations II
A clear explanation of Permutations II using sorting, depth-first search, and duplicate-skipping backtracking.
LeetCode 626: Exchange Seats
A SQL solution for swapping every pair of adjacent student seats while leaving the final seat unchanged when the row count is odd.
LeetCode 593: Valid Square
A clear geometry solution for checking whether four unordered points form a valid square.
LeetCode 588: Design In-Memory File System
A clear design guide for implementing an in-memory file system with directory listing, directory creation, file append, and file read operations.
LeetCode 561: Array Partition
A clear explanation of Array Partition using sorting and adjacent pairing to maximize the sum of pair minimums.
LeetCode 539: Minimum Time Difference
A clear explanation of finding the minimum difference between 24-hour clock times using minute conversion and sorting.
LeetCode 527: Word Abbreviation
A clear explanation of generating minimal unique word abbreviations using grouping and trie prefixes.
LeetCode 522: Longest Uncommon Subsequence II
A clear explanation of finding the longest uncommon subsequence among many strings using subsequence checks.
LeetCode 506: Relative Ranks
A clear explanation of assigning athlete ranks from scores using sorting while preserving original indices.
LeetCode 502: IPO
A clear explanation of maximizing capital by selecting at most k projects using sorting and a max heap.
LeetCode 475: Heaters
A clear explanation of finding the minimum heater radius by sorting positions and matching each house to its nearest heater.
LeetCode 462: Minimum Moves to Equal Array Elements II
A clear explanation of why the median minimizes the number of moves needed to make all array elements equal.
LeetCode 455: Assign Cookies
A clear explanation of the greedy two-pointer solution for maximizing the number of content children.
LeetCode 452: Minimum Number of Arrows to Burst Balloons
A clear explanation of the greedy interval solution for finding the minimum number of arrows needed to burst all balloons.
LeetCode 451: Sort Characters By Frequency
A clear explanation of sorting characters by decreasing frequency using a hash map and sorting.
LeetCode 436: Find Right Interval
Find, for each interval, the interval with the smallest start point greater than or equal to its end point using sorting and binary search.
LeetCode 435: Non-overlapping Intervals
Remove the minimum number of intervals so the remaining intervals do not overlap, using greedy sorting by end time.
LeetCode 414: Third Maximum Number
A clear explanation of finding the third distinct maximum number using one pass and constant space.
LeetCode 406: Queue Reconstruction by Height
A clear explanation of reconstructing a queue using greedy sorting and indexed insertion.
LeetCode 368: Largest Divisible Subset
A clear explanation of finding the largest subset where every pair is divisible using sorting, dynamic programming, and parent reconstruction.
LeetCode 360: Sort Transformed Array
A clear explanation of sorting values after applying a quadratic function using two pointers.
LeetCode 354: Russian Doll Envelopes
A clear explanation of solving Russian Doll Envelopes using sorting and longest increasing subsequence.
LeetCode 350: Intersection of Two Arrays II
A clear explanation of Intersection of Two Arrays II using frequency counting.
LeetCode 349: Intersection of Two Arrays
A clear explanation of Intersection of Two Arrays using hash sets for uniqueness and fast lookup.
LeetCode 296: Best Meeting Point
A median-based solution for minimizing total Manhattan distance in a grid.
LeetCode 280: Wiggle Sort
A greedy in-place solution for rearranging an array into a non-strict wiggle pattern.
LeetCode 274: H-Index
A clear explanation of the H-Index problem using sorting, then an optimized counting approach.
LeetCode 253: Meeting Rooms II
A clear explanation of the Meeting Rooms II problem using a min heap to track active meeting end times.
LeetCode 252: Meeting Rooms
A clear explanation of the Meeting Rooms problem using interval sorting to detect overlaps.
LeetCode 88: Merge Sorted Array
A detailed guide to solving Merge Sorted Array in-place by merging from the back with three pointers.
LeetCode 179: Largest Number
A clear explanation of arranging non-negative integers to form the largest possible concatenated number using a custom sort order.
LeetCode 169: Majority Element
A clear explanation of finding the element that appears more than half the time using Boyer-Moore voting.
LeetCode 164: Maximum Gap
A clear explanation of finding the maximum adjacent gap in sorted order using buckets and the pigeonhole principle.
LeetCode 147: Insertion Sort List
Sort a singly linked list using insertion sort by splicing each node into a growing sorted list.
LeetCode 75: Sort Colors
A clear guide to sorting an array of 0s, 1s, and 2s in place using the Dutch National Flag algorithm.
LeetCode 56: Merge Intervals
A clear guide to solving Merge Intervals by sorting intervals and merging them in one pass.
LeetCode 40: Combination Sum II
A clear explanation of finding unique combinations that sum to a target when each array element may be used at most once.
LeetCode 18: 4Sum
A detailed explanation of finding all unique quadruplets that sum to a target using sorting and two pointers.
LeetCode 16: 3Sum Closest
A detailed explanation of finding the sum of three integers closest to a target using sorting and two pointers.
LeetCode 15: 3Sum
A detailed explanation of finding all unique triplets that sum to zero using sorting and two pointers.
Suffix Array Radix Sort
Construct a suffix array by sorting rank pairs with radix or counting sort during the doubling method.
Burstsort String Sorting
String sorting method that groups strings by prefixes in a trie and sorts leaf buckets for cache efficient lexicographic order.
Burstsort
Cache efficient string sorting algorithm that builds a trie and sorts buckets lazily for high performance on large text data.
LSD Radix Sort
Sort fixed width keys by processing digits from least significant to most significant using a stable inner sort.
Radix Sort
Sort integer or string keys by processing one digit, byte, or character position at a time.
11. Parallel, Distributed, and GPU Sorting
High-throughput sorting: parallel merge and quicksort, GPU bitonic and radix sort, SIMD sorting networks, and distributed partition-based sorts.
10. External Memory, Cache, and Database Sorting
Sorting beyond main memory: external merge sort, polyphase merge, cache-oblivious techniques, LSM compaction, and database sort phases.
9. Partial, Online, and Adaptive Sorting
Sorting under constraints: partial sort, online insertion, adaptive merge, Timsort internals, and lazy or order-maintenance sorting.
8. Integer and Distribution Sorting
Non-comparison sorts: counting, radix, and bucket sort families, string sorting, and suffix array construction.
7. Divide and Conquer Sorting
Divide-and-conquer sorts: merge sort variants, quicksort family, heapsort, and comparison-based sorting networks.
6. Elementary Sorting
Elementary comparison-based sorts: bubble, selection, insertion, Shell, comb, cycle, and curiosity sorts.
01. Searching and Sorting
Searching and sorting techniques spanning sequential and parallel algorithms, from linear scan to GPU-based distribution sort.
Shear Sort
Sort a two dimensional mesh by alternating row sorts and column sorts until the grid is globally ordered.
Bitonic Sort on Hypercube
Sort distributed keys across hypercube processors using dimension based compare and exchange stages.
Parallel Sorting by Regular Sampling (PSRS)
Sort data in parallel by local sorting, regular sampling, global splitter selection, redistribution, and final local merge.
Distributed Range Partition Sort
Sort distributed data by assigning fixed key ranges to workers, routing records by range, then sorting locally.
Distributed Sample Sort
Sort data across machines by sampling keys, choosing splitters, redistributing records into ordered buckets, and sorting buckets locally.
TeraSort
Sort very large datasets with range partitioning, distributed shuffle, and reducer local sorting.
MapReduce Sort
Sort large distributed datasets by partitioning records by key range, sorting partitions locally, and writing ordered output shards.
Bitonic Merge Network
Merge a bitonic sequence into a sorted sequence using a fixed comparator network.
Odd Even Sorting Network
Sort a fixed size sequence using a data independent network of odd even compare exchange stages.
Bitonic Sorting Network
Sort a fixed size sequence with a bitonic compare and exchange network whose schedule is independent of input values.
SIMD Sorting Network
Sort a fixed size vector by mapping a data independent sorting network to SIMD compare, shuffle, and blend operations.
SIMD Bitonic Sort
Sort small vectors using SIMD registers with a fixed bitonic compare exchange network.
CUDA Block Sort
Sort a block sized tile on the GPU using shared memory and cooperative threads.
CUDA Warp Sort
Sort a small set of values inside one CUDA warp using shuffle operations and compare exchange steps.
GPU Sample Sort
Sort data on a GPU by selecting splitters, partitioning into buckets in parallel, then sorting buckets independently.
GPU Merge Sort
Sort data on a GPU by recursively merging sorted runs using parallel merge primitives.
GPU Radix Sort
Sort fixed width keys on a GPU using digit passes, parallel histograms, prefix sums, and scatter operations.
GPU Bitonic Sort
Sort data on a GPU using a regular bitonic compare and exchange network.
Parallel Counting Sort
Count key frequencies in parallel, compute prefix sums, then scatter elements into sorted positions.
Parallel Odd Even Sort
Sort an array by repeatedly comparing odd indexed and even indexed adjacent pairs in parallel.
Parallel Bitonic Sort
Sort data by building and merging bitonic sequences through a regular compare and exchange network.
Parallel Radix Sort
Sort integer keys by processing fixed width digit groups in parallel using counting and prefix sums.
Parallel Sample Sort
Choose splitters from samples, partition the input into buckets, sort buckets independently, then concatenate the sorted buckets.
Parallel Quicksort
Partition the array around a pivot, then sort partitions concurrently using parallel recursion.
Parallel Merge Sort
Divide the input, sort subarrays in parallel, then merge them using parallel merge procedures.
K Way Winner Tree Merge
K-way merge using a tournament tree that stores winners at internal nodes and repeatedly updates the winning path.
K Way Loser Tree Merge
Efficient k-way merge using a tournament tree that stores losers to reduce comparisons and improve external merge performance.
External Bucket Sort
External-memory bucket sort that partitions records into ordered buckets stored on disk and sorts each bucket separately.
External Sample Sort
External-memory sorting algorithm that uses sampling to partition data into balanced buckets, then sorts each bucket independently.
External Radix Sort
External-memory radix sort that processes large datasets by distributing records into digit-based buckets across multiple passes.
Parallel External Merge Sort
External sorting algorithm that performs run generation and merging concurrently across multiple processors and disks.
Spill Sort
Sorting method that keeps data in memory until a memory limit is reached, then spills sorted runs to external storage and merges them.
Chunked Sort
Sorting method that divides input into bounded-size chunks, sorts each chunk independently, and then combines the chunks.
Memory Mapped External Sort
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.
Tape Merge Sort
External sorting algorithm that distributes sorted runs across sequential storage tapes and repeatedly merges them.
Replacement Selection Run Generation
External sorting technique that uses a heap to produce initial sorted runs longer than the available memory.
Sort Merge Join Sort Phase
The sorting stage used before a sort-merge join when one or both inputs are not already ordered by the join key.
Database External Sort
External sorting procedure used by database systems for ORDER BY, GROUP BY, DISTINCT, and sort-merge joins.
LSM Tree Compaction Sort
Sorting through hierarchical merging in Log Structured Merge Trees using compaction across levels.
B Tree Bulk Load Sort
Sorting method that builds a B-tree directly from sorted data using bulk loading to minimize I/O operations.
Buffer Tree Sort
External-memory sorting method that inserts records into a buffered tree and extracts them in sorted order.
Funnel Sort
Cache oblivious sorting algorithm that achieves optimal memory transfer complexity using recursive multiway merging structures called funnels.
Cache Oblivious Sorting
Sorting techniques that achieve good cache behavior without explicitly knowing cache size or block size.
Cache Aware Sorting
Sorting techniques that explicitly use knowledge of cache size and block size to minimize memory hierarchy cost.
Distribution Sweeping Sort
External-memory sorting method that partitions data into key ranges, sorts each range, and concatenates the sorted partitions.
Cascade Merge Sort
External sorting method that merges sorted runs through staged levels so output from one level feeds the next.
Balanced K Way Merge Sort
External sorting algorithm that repeatedly merges groups of k sorted runs until one final sorted run remains.
Polyphase Merge Sort
External sorting algorithm that distributes sorted runs unevenly across files so repeated merges need fewer empty files and less redistribution.
Two Phase Multiway Merge Sort
External sorting algorithm that performs run generation and a single multiway merge using limited memory.
External Merge Sort
Sort data that does not fit in memory by dividing it into sorted runs and merging them using external storage.
Order Maintenance Sort
Maintain a dynamically ordered sequence under insertions and comparisons without fully re-sorting.
Lazy Selection Sort
Select the next smallest element on demand, avoiding full sorting until all elements are requested.
Lazy Sort
Delay sorting work until ordered output or ordered queries are actually needed.
Tournament Tree Partial Sort
Use a tournament tree to extract the smallest or largest k elements in sorted order without fully sorting the input.
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.
External Replacement Selection
Generate long initial runs for external sorting using replacement selection with disk-based streams.
Rolling Median Sort
Maintain the median of a sliding window using two heaps while the window moves over a stream.
Sliding Window Sort
Maintain sorted order over a moving window of the most recent elements in a stream.
Stream Sort by Buffer
Sort a stream in bounded chunks by buffering records, sorting each chunk, and emitting sorted runs or partially ordered output.
Binary Tree Online Sort
Maintain a sorted sequence by inserting elements into a binary search tree as they arrive and extracting them in order.
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.
Online Topological Sort
Maintain a valid topological ordering of a directed acyclic graph as vertices or edges are added over time.
Patience Sort with Piles
Sort a sequence by building piles using patience sorting and then merging them.
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.
Galloping Merge
Accelerate merging by switching from one-by-one comparison to exponential search when one run wins repeatedly.
Timsort Run Detection
Detect natural runs in input and normalize them for efficient merging in Timsort.
Min Heap K Sorted Sort
Sort a k-sorted array using a sliding min heap window of size k+1.
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.
Replacement Selection
Generate long sorted runs from a stream using a heap, commonly used in external sorting.
Patience Sorting for LIS
Use patience sorting to compute the length and structure of the longest increasing subsequence efficiently.
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.
Online Insertion Sort
Sort a sequence as elements arrive by inserting each new item into its correct position among the items already seen.
Incremental Sort
Maintain a sorted sequence while elements are inserted one by one, updating order incrementally.
Top K Sort
Extract and sort the top k elements (smallest or largest) from a sequence without fully sorting it.
Partial Sort
Rearrange a sequence so that the smallest k elements appear in sorted order, without fully sorting the entire sequence.
Signed Integer Radix Sort
Radix sort for signed integers by transforming values to preserve ordering across negative and positive ranges.
Floating Point Radix Sort
Radix sort for floating-point numbers by transforming their bit representation to preserve numeric order.
DC7 Suffix Array Sort
Difference cover modulo 7 suffix array construction method that generalizes DC3 with a larger recursive sample.
DC3 Suffix Array Sort
Difference cover modulo 3 algorithm for linear-time suffix array construction using radix sorting and merging.
Skew Suffix Array Sort
Linear-time suffix array construction using the DC3 algorithm that recursively sorts positions modulo 3.
SA IS
Linear-time suffix array construction algorithm based on induced sorting of LMS suffixes.
Induced Sorting
Linear-time technique for suffix array construction that induces order of suffixes from a subset of sorted suffixes.
Least Significant Byte Sort
LSD radix sort variant that processes keys byte by byte from least significant to most significant.
Bytewise Radix Sort
Radix sort that processes fixed-width keys one byte at a time using 256 counting buckets.
Word Radix Sort
Radix sort specialized for fixed-width machine words using byte or bit extraction for high throughput.
Sparse Key Counting Sort
Counting sort variant that stores counts only for keys that appear, avoiding dense arrays over large key ranges.
Coordinate Compression Sort
Sort values by mapping them to a dense rank space and ordering by compressed indices.
Counting Sort with Negative Keys
Extend counting sort to handle negative integers by shifting keys into a nonnegative index range.
Suffix Array Doubling Sort
Construct a suffix array by iteratively sorting suffixes using doubling technique with rank pairs.
Three Way String Quicksort
String sorting algorithm that uses three-way partitioning on characters to efficiently handle repeated prefixes.
Multikey Quicksort
String sorting algorithm that partitions strings by the character at the current depth using three-way quicksort.
American Flag String Sort
In-place MSD radix string sort that partitions strings by character using American flag style bucket permutation.
Most Significant Byte Sort
MSD radix sort variant that partitions keys by the most significant byte and recursively sorts subarrays.
Integer Sample Sort
Sample sort specialized for integer keys using range-based partitioning and optional radix-style bucket classification.
IPS4o
In-place parallel super scalar samplesort for high performance comparison sorting on modern multicore machines.
Ska Sort
High performance radix sort variant using cache friendly block partitioning and branchless techniques.
Radix Exchange Sort
In place binary radix sort that partitions keys by bits from most significant to least significant.
Spreadsort
Hybrid distribution and comparison sort that adapts between radix-like partitioning and comparison sorting.
Flashsort
Distribution sorting algorithm that approximates uniform distribution and then refines with insertion sort.
Pigeonhole Sort
Sort integer keys by placing each value into a direct address slot over a small contiguous range.
Histogram Sort
Sort elements by building a frequency histogram and reconstructing the output from cumulative counts.
Uniform Bucket Sort
Bucket sort variant that assumes uniform distribution and uses equal-width buckets with simple mapping.
Bucket Sort
Distribute elements into buckets based on value ranges and sort each bucket independently.
Binary Radix Sort
Sort integers by processing bits directly using partitioning instead of counting arrays.
Counting Sort
Sort integers by counting occurrences of each key and reconstructing the output in linear time.
In Place Radix Sort
Sort digit based keys by redistributing elements inside the original array with only small auxiliary bucket state.
American Flag Sort
In place radix sort that partitions elements by digit using cycle leader permutation.
MSD Radix Sort
Sort keys by processing the most significant digit first and recursively sorting subarrays.
Key Indexed Counting
Counting-based stable sorting technique that maps keys to index ranges using frequency and prefix sums.
Stable Counting Sort
Stable variant of counting sort using prefix sums to preserve relative order of equal keys.
Tournament Merge Sort
Merge-based sorting algorithm that uses a tournament tree to repeatedly select the next smallest element.
Multiway Merge Sort
Merge sort variant that merges more than two sorted sequences at each step.
Sample Sort
Divide and conquer sorting algorithm that uses sampling to partition data into balanced buckets.
Cache Oblivious Merge Sort
Merge sort variant that improves locality without tuning parameters for a specific cache size.
Cache Efficient Merge Sort
Merge sort variant designed to improve cache locality by structuring recursion and merging to fit memory hierarchies.
Batcher Merge Sort
Sorting network algorithm based on recursively sorting halves and merging them with Batcher's odd even merge network.
Pairwise Sorting Network
Sorting network that sorts by repeatedly applying pairwise compare and swap stages.
Odd Even Merge Sort
Sorting network algorithm that recursively merges sorted sequences using odd even comparisons.
Bitonic Sort
Comparison sorting algorithm that sorts a bitonic sequence using structured compare and swap operations.
Ford Johnson Sort
Comparison optimal sorting algorithm that minimizes comparisons using a structured insertion schedule.
Merge Insertion Sort
Comparison-optimal sorting algorithm that combines merging and insertion guided by a structured schedule.
Weak Heapsort
Heapsort variant based on weak heaps, reducing the number of comparisons while retaining in-place sorting.
Ternary Heapsort
Heapsort variant that uses a ternary heap with three children per node.
Bottom Up Heapsort
Heapsort variant that uses bottom up sift down to reduce comparisons during heapify.
Heapsort
Comparison sorting algorithm that builds a heap and repeatedly extracts the maximum.
Lomuto Partition Quicksort
Quicksort variant using the Lomuto single-index partition scheme.
Hoare Partition Quicksort
Quicksort variant that uses Hoare's two pointer partition scheme.
Quicksort Ninther
Quicksort variant that selects the pivot using Tukey's ninther, the median of three medians of three.
Quicksort Median of Three
Quicksort variant that chooses the pivot as the median of the first, middle, and last elements.
Stable Quicksort
Quicksort variant that preserves the relative order of equal elements.
Block Quicksort
Quicksort variant that processes elements in blocks to reduce branch misprediction and improve cache efficiency.
Pattern Defeating Quicksort
Quicksort variant that detects and avoids bad input patterns using adaptive partitioning and pivot selection.
Introsort
Hybrid sorting algorithm that starts with quicksort and falls back to heapsort when recursion becomes too deep.
Dual Pivot Quicksort
Quicksort variant that partitions the array using two pivots into three regions.
Three Way Quicksort
Quicksort variant that partitions into less than, equal to, and greater than pivot.
Randomized Quicksort
Quicksort variant that selects pivots randomly to avoid worst case patterns.
Quicksort
Divide and conquer sorting algorithm that partitions the array around a pivot and recursively sorts both sides.
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.
Block Merge Sort
Stable merge sort variant that uses block rearrangement and a small buffer to reduce auxiliary memory.
In Place Merge Sort
Merge sort variant that reduces auxiliary memory by merging sorted ranges inside the original array.
Natural Merge Sort
Adaptive merge sort that detects existing sorted runs and merges them.
Bottom Up Merge Sort
Iterative merge sort that builds sorted runs from size 1 upward without recursion.
Top Down Merge Sort
Recursive merge sort that splits the array from the top and merges sorted halves.
Merge Sort
Divide and conquer sorting algorithm that splits the array, sorts recursively, and merges in linear time.
Exchange Sort
A simple quadratic sorting algorithm that compares all pairs and swaps out-of-order elements.
Bingo Sort
Repeatedly place all occurrences of the current minimum value before moving to the next distinct value.
Cartesian Tree Sort
Sort by building a Cartesian tree and extracting elements via inorder traversal.
Weak Heap Sort
A variant of heapsort using weak heaps with fewer comparisons.
Smoothsort
An adaptive in-place comparison sort based on Leonardo heaps.
Tournament Sort
Sort by repeatedly selecting the minimum element using a tournament tree.
Tree Sort
Insert all elements into a binary search tree, then traverse the tree in sorted order.
Patience Sort
Sort by building piles using patience card game rules and then merging them.
Library Sort
An insertion-based sorting algorithm that leaves gaps between elements to reduce shifting.
Strand Sort
Extract increasing subsequences and merge them to form a sorted sequence.
Bead Sort
Sort non-negative integers by simulating gravity on beads arranged in columns.
Slow Sort
A deliberately inefficient recursive sorting algorithm based on divide and conquer followed by maximum placement.
Stooge Sort
A recursive sorting algorithm with extremely poor performance based on overlapping subproblems.
Pancake Sort
Sort by repeatedly flipping prefixes to move the maximum element to its correct position.
Cycle Sort
Minimizes writes by placing each element directly into its correct position using cycles.
Comb Sort
A bubble-sort variant that compares elements at a shrinking gap to remove long-distance inversions early.
Shell Sort with Sedgewick Gaps
Shell sort using Sedgewick gap sequence for improved practical performance.
Shell Sort with Hibbard Gaps
Shell sort using Hibbard gap sequence 1, 3, 7, 15, ..., improving over simple halving.
Shell Sort with Shell Gaps
Shell sort using the original gap sequence n/2, n/4, ..., 1.
Shell Sort
Generalization of insertion sort that compares elements at a gap, reducing long-distance inversions early.
Binary Insertion Sort
Insertion sort that uses binary search to find the insertion position, reducing comparisons.
Insertion Sort
Build a sorted sequence by inserting each element into its correct position.
Double Selection Sort
Select both minimum and maximum elements in each pass and place them at the beginning and end.
Stable Selection Sort
A stable variant of selection sort that preserves the relative order of equal elements by shifting instead of swapping.
Selection Sort
Repeatedly select the minimum element from the unsorted portion and place it at the beginning.
Gnome Sort
A simple sorting algorithm that moves elements backward when out of order, similar to insertion sort with swaps.
Odd Even Sort
A variation of bubble sort that alternates between comparing odd-even and even-odd index pairs.
Bubble Sort
Repeatedly swap adjacent elements that are out of order until the sequence becomes sorted.
Cocktail Shaker Sort
A bidirectional variant of bubble sort that alternates passes from left to right and right to left.
Optimized Bubble Sort
Bubble sort with early termination when no swaps occur, reducing unnecessary passes on nearly sorted data.
SA-IS Suffix Array Construction
Linear time suffix array construction using induced sorting of LMS substrings.
DC7 Suffix Array Sort
Generalized divide and conquer suffix array construction using modulo 7 partitioning.
Skew Suffix Array Sort (DC3)
Linear time suffix array construction using the DC3 divide and conquer strategy.
Suffix Array Doubling Sort
Build a suffix array using the prefix doubling technique with iterative ranking.
6.25 Choosing the Right Sort
Select the appropriate sorting algorithm based on input size, data characteristics, memory constraints, and required guarantees such as stability or worst-case bounds.
6.24 Common Bugs
Identify boundary errors, broken invariants, and comparator mistakes that cause sorting implementations to fail on edge cases or duplicate-heavy inputs.
6.23 Testing Sort Correctness
Verify both the ordering and permutation properties of sorting implementations using randomized, edge-case, and adversarial test strategies.
6.22 Parallel Sorting
Distribute sorting work across multiple processors to reduce wall-clock time, with analysis of total work, span, communication, and synchronization.
6.21 Lower Bounds for Sorting
Prove that any comparison-based sorting algorithm requires Ω(n log n) comparisons in the worst case using a decision tree argument.
6.20 Inversion Counting
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.
6.19 Coordinate Compression
Replace large or sparse keys with small dense ranks that preserve order, making range-based and indexed structures practical on wide-valued data.
6.18 Sorting Records
Sort structured values by one or more fields while moving the full record, with attention to key extraction, stability, and multi-key ordering.
6.17 Custom Comparators
Define correct comparison relations for user-defined types and non-trivial orderings — consistency requirements that sorting correctness depends on.
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.
6.15 External Sorting
Sort datasets that exceed main memory by organizing the algorithm around sequential disk access, merge passes, and minimizing I/O operations.
6.14 Median Selection
Find the middle value of a collection in linear time using selection algorithms, without the overhead of a full sort.
6.13 Quickselect
Find the element at a given rank using quicksort's partition step but recursing into only one side, achieving expected linear time.
6.12 Top k Selection
Find the largest or smallest k elements without sorting the full input, using a heap or partition-based approach.
6.11 Partial Sorting
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.
6.10 Stable Sorting
A stable sort preserves the original relative order of equal keys — an extra guarantee required when sorting by secondary fields or compound criteria.
6.9 Bucket Sort
Distribute elements into buckets by value range, sort each bucket, then concatenate — achieving linear expected time on uniformly distributed input.
6.8 Radix Sort
Sort keys digit by digit using a stable subroutine, achieving linear time for fixed-width integers without any key comparisons.
6.7 Counting Sort
Sort integer keys from a small range in linear time by counting occurrences and reconstructing the output from those counts.
6.6 Heap Sort
Build a max-heap in place, then repeatedly extract the maximum to produce a sorted array in O(n log n) worst-case time.
6.5 Quick Sort
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.
6.4 Merge Sort
Divide the input into halves, recursively sort each half, then merge them — combining local order into global order in O(n log n) time.
6.3 Insertion Sort
Build a sorted prefix one element at a time by inserting each new element into its correct position within the already-sorted portion.
6.2 Selection Sort
Sort by repeatedly selecting the minimum element from the unsorted suffix and placing it into the next output position.
6.1 Sorting Contracts
A sorting algorithm is correct only when its output is both ordered and a permutation of the input — two properties every implementation must preserve.
3.7 Merge Two Sorted Lists
Merging combines two sorted singly linked lists into one sorted list by relinking nodes.
Chapter 6. Sorting
Sorting algorithms from fundamental contracts through comparison-based, linear-time, and specialized variants, with selection, external sorting, and correctness analysis.