Skip to content

7. Divide and Conquer Sorting

Divide-and-conquer sorts: merge sort variants, quicksort family, heapsort, and comparison-based sorting networks.

algorithms sorting divide-and-conquer
indexslugname
181merge-sortMerge Sort
182top-down-merge-sortTop Down Merge Sort
183bottom-up-merge-sortBottom Up Merge Sort
184natural-merge-sortNatural Merge Sort
185in-place-merge-sortIn Place Merge Sort
186block-merge-sortBlock Merge Sort
187timsortTimsort
188powersortPowersort
189quicksortQuicksort
190randomized-quicksortRandomized Quicksort
191three-way-quicksortThree Way Quicksort
192dual-pivot-quicksortDual Pivot Quicksort
193introsortIntrosort
194pdqsortPattern Defeating Quicksort
195block-quicksortBlock Quicksort
196stable-quicksortStable Quicksort
197quicksort-median-of-threeQuicksort Median of Three
198quicksort-nintherQuicksort Ninther
199quicksort-hoare-partitionHoare Partition Quicksort
200quicksort-lomuto-partitionLomuto Partition Quicksort
201heapsortHeapsort
202bottom-up-heapsortBottom Up Heapsort
203ternary-heapsortTernary Heapsort
204weak-heapsortWeak Heapsort
205merge-insertion-sortMerge Insertion Sort
206ford-johnson-sortFord Johnson Sort
207bitonic-sortBitonic Sort
208odd-even-merge-sortOdd Even Merge Sort
209pairwise-sorting-networkPairwise Sorting Network
210batcher-merge-sortBatcher Merge Sort
211akra-bazzi-merge-sort-variantAkra Bazzi Merge Sort Variant
212cache-oblivious-merge-sortCache Oblivious Merge Sort
213sample-sortSample Sort
214multiway-merge-sortMultiway Merge Sort
215tournament-merge-sortTournament Merge Sort
Merge SortDivide and conquer sorting algorithm that splits the array, sorts recursively, and merges in linear time.
3 min
Top Down Merge SortRecursive merge sort that splits the array from the top and merges sorted halves.
3 min
Bottom Up Merge SortIterative merge sort that builds sorted runs from size 1 upward without recursion.
3 min
Natural Merge SortAdaptive merge sort that detects existing sorted runs and merges them.
4 min
In Place Merge SortMerge sort variant that reduces auxiliary memory by merging sorted ranges inside the original array.
4 min
Block Merge SortStable merge sort variant that uses block rearrangement and a small buffer to reduce auxiliary memory.
4 min
TimsortAdaptive stable sorting algorithm that combines merge sort with run detection and insertion sort.
3 min
PowersortStable adaptive merge sort that uses power based ordering of runs for near optimal merging.
3 min
QuicksortDivide and conquer sorting algorithm that partitions the array around a pivot and recursively sorts both sides.
3 min
Randomized QuicksortQuicksort variant that selects pivots randomly to avoid worst case patterns.
3 min
Three Way QuicksortQuicksort variant that partitions into less than, equal to, and greater than pivot.
3 min
Dual Pivot QuicksortQuicksort variant that partitions the array using two pivots into three regions.
4 min
IntrosortHybrid sorting algorithm that starts with quicksort and falls back to heapsort when recursion becomes too deep.
4 min
Pattern Defeating QuicksortQuicksort variant that detects and avoids bad input patterns using adaptive partitioning and pivot selection.
3 min
Block QuicksortQuicksort variant that processes elements in blocks to reduce branch misprediction and improve cache efficiency.
3 min
Stable QuicksortQuicksort variant that preserves the relative order of equal elements.
3 min
Quicksort Median of ThreeQuicksort variant that chooses the pivot as the median of the first, middle, and last elements.
4 min
Quicksort NintherQuicksort variant that selects the pivot using Tukey's ninther, the median of three medians of three.
4 min
Hoare Partition QuicksortQuicksort variant that uses Hoare's two pointer partition scheme.
3 min
Lomuto Partition QuicksortQuicksort variant using the Lomuto single-index partition scheme.
3 min
HeapsortComparison sorting algorithm that builds a heap and repeatedly extracts the maximum.
3 min
Bottom Up HeapsortHeapsort variant that uses bottom up sift down to reduce comparisons during heapify.
3 min
Ternary HeapsortHeapsort variant that uses a ternary heap with three children per node.
3 min
Weak HeapsortHeapsort variant based on weak heaps, reducing the number of comparisons while retaining in-place sorting.
4 min
Merge Insertion SortComparison-optimal sorting algorithm that combines merging and insertion guided by a structured schedule.
3 min
Ford Johnson SortComparison optimal sorting algorithm that minimizes comparisons using a structured insertion schedule.
3 min
Bitonic SortComparison sorting algorithm that sorts a bitonic sequence using structured compare and swap operations.
3 min
Odd Even Merge SortSorting network algorithm that recursively merges sorted sequences using odd even comparisons.
3 min
Pairwise Sorting NetworkSorting network that sorts by repeatedly applying pairwise compare and swap stages.
2 min
Batcher Merge SortSorting network algorithm based on recursively sorting halves and merging them with Batcher's odd even merge network.
3 min
Cache Efficient Merge SortMerge sort variant designed to improve cache locality by structuring recursion and merging to fit memory hierarchies.
3 min
Cache Oblivious Merge SortMerge sort variant that improves locality without tuning parameters for a specific cache size.
4 min
Sample SortDivide and conquer sorting algorithm that uses sampling to partition data into balanced buckets.
3 min
Multiway Merge SortMerge sort variant that merges more than two sorted sequences at each step.
2 min
Tournament Merge SortMerge-based sorting algorithm that uses a tournament tree to repeatedly select the next smallest element.
3 min