7. Divide and Conquer Sorting

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

35 items

7. Divide and conquer sorting, 35

index slug name
181 merge-sort Merge Sort
182 top-down-merge-sort Top Down Merge Sort
183 bottom-up-merge-sort Bottom Up Merge Sort
184 natural-merge-sort Natural Merge Sort
185 in-place-merge-sort In Place Merge Sort
186 block-merge-sort Block Merge Sort
187 timsort Timsort
188 powersort Powersort
189 quicksort Quicksort
190 randomized-quicksort Randomized Quicksort
191 three-way-quicksort Three Way Quicksort
192 dual-pivot-quicksort Dual Pivot Quicksort
193 introsort Introsort
194 pdqsort Pattern Defeating Quicksort
195 block-quicksort Block Quicksort
196 stable-quicksort Stable Quicksort
197 quicksort-median-of-three Quicksort Median of Three
198 quicksort-ninther Quicksort Ninther
199 quicksort-hoare-partition Hoare Partition Quicksort
200 quicksort-lomuto-partition Lomuto Partition Quicksort
201 heapsort Heapsort
202 bottom-up-heapsort Bottom Up Heapsort
203 ternary-heapsort Ternary Heapsort
204 weak-heapsort Weak Heapsort
205 merge-insertion-sort Merge Insertion Sort
206 ford-johnson-sort Ford Johnson Sort
207 bitonic-sort Bitonic Sort
208 odd-even-merge-sort Odd Even Merge Sort
209 pairwise-sorting-network Pairwise Sorting Network
210 batcher-merge-sort Batcher Merge Sort
211 akra-bazzi-merge-sort-variant Akra Bazzi Merge Sort Variant
212 cache-oblivious-merge-sort Cache Oblivious Merge Sort
213 sample-sort Sample Sort
214 multiway-merge-sort Multiway Merge Sort
215 tournament-merge-sort Tournament Merge Sort
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Merge Sort

Divide and conquer sorting algorithm that splits the array, sorts recursively, and merges in linear time.
algorithms sorting merge-sort divide-and-conquer
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Top Down Merge Sort

Recursive merge sort that splits the array from the top and merges sorted halves.
algorithms sorting merge-sort divide-and-conquer
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Bottom Up Merge Sort

Iterative merge sort that builds sorted runs from size 1 upward without recursion.
algorithms sorting merge-sort iterative
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Natural Merge Sort

Adaptive merge sort that detects existing sorted runs and merges them.
algorithms sorting merge-sort adaptive
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

In Place Merge Sort

Merge sort variant that reduces auxiliary memory by merging sorted ranges inside the original array.
algorithms sorting merge-sort in-place
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Block Merge Sort

Stable merge sort variant that uses block rearrangement and a small buffer to reduce auxiliary memory.
algorithms sorting merge-sort block-merge-sort
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Timsort

Adaptive stable sorting algorithm that combines merge sort with run detection and insertion sort.
algorithms sorting timsort adaptive
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Powersort

Stable adaptive merge sort that uses power based ordering of runs for near optimal merging.
algorithms sorting powersort adaptive
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Quicksort

Divide and conquer sorting algorithm that partitions the array around a pivot and recursively sorts both sides.
algorithms sorting quicksort divide-and-conquer
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Randomized Quicksort

Quicksort variant that selects pivots randomly to avoid worst case patterns.
algorithms sorting quicksort randomized
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Three Way Quicksort

Quicksort variant that partitions into less than, equal to, and greater than pivot.
algorithms sorting quicksort three-way-partition
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Dual Pivot Quicksort

Quicksort variant that partitions the array using two pivots into three regions.
algorithms sorting quicksort dual-pivot
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Introsort

Hybrid sorting algorithm that starts with quicksort and falls back to heapsort when recursion becomes too deep.
algorithms sorting introsort hybrid-sort
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Pattern Defeating Quicksort

Quicksort variant that detects and avoids bad input patterns using adaptive partitioning and pivot selection.
algorithms sorting pdqsort quicksort
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Block Quicksort

Quicksort variant that processes elements in blocks to reduce branch misprediction and improve cache efficiency.
algorithms sorting quicksort block-partition
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Stable Quicksort

Quicksort variant that preserves the relative order of equal elements.
algorithms sorting quicksort stable-sort
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Quicksort Median of Three

Quicksort variant that chooses the pivot as the median of the first, middle, and last elements.
algorithms sorting quicksort pivot-selection
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Quicksort Ninther

Quicksort variant that selects the pivot using Tukey's ninther, the median of three medians of three.
algorithms sorting quicksort pivot-selection
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Hoare Partition Quicksort

Quicksort variant that uses Hoare's two pointer partition scheme.
algorithms sorting quicksort partition
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Lomuto Partition Quicksort

Quicksort variant using the Lomuto single-index partition scheme.
algorithms sorting quicksort partition
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Heapsort

Comparison sorting algorithm that builds a heap and repeatedly extracts the maximum.
algorithms sorting heapsort heap
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Bottom Up Heapsort

Heapsort variant that uses bottom up sift down to reduce comparisons during heapify.
algorithms sorting heapsort heap
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Ternary Heapsort

Heapsort variant that uses a ternary heap with three children per node.
algorithms sorting heapsort heap
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Weak Heapsort

Heapsort variant based on weak heaps, reducing the number of comparisons while retaining in-place sorting.
algorithms sorting heapsort weak-heap
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Merge Insertion Sort

Comparison-optimal sorting algorithm that combines merging and insertion guided by a structured schedule.
algorithms sorting merge-insertion optimal-comparisons
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Ford Johnson Sort

Comparison optimal sorting algorithm that minimizes comparisons using a structured insertion schedule.
algorithms sorting ford-johnson optimal-comparisons
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Bitonic Sort

Comparison sorting algorithm that sorts a bitonic sequence using structured compare and swap operations.
algorithms sorting bitonic-sort sorting-network
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Odd Even Merge Sort

Sorting network algorithm that recursively merges sorted sequences using odd even comparisons.
algorithms sorting sorting-network odd-even-merge
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Pairwise Sorting Network

Sorting network that sorts by repeatedly applying pairwise compare and swap stages.
algorithms sorting sorting-network pairwise
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Batcher Merge Sort

Sorting network algorithm based on recursively sorting halves and merging them with Batcher's odd even merge network.
algorithms sorting sorting-network batcher-merge-sort
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Cache Efficient Merge Sort

Merge sort variant designed to improve cache locality by structuring recursion and merging to fit memory hierarchies.
algorithms sorting merge-sort cache-efficient
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Cache Oblivious Merge Sort

Merge sort variant that improves locality without tuning parameters for a specific cache size.
algorithms sorting merge-sort cache-oblivious
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Sample Sort

Divide and conquer sorting algorithm that uses sampling to partition data into balanced buckets.
algorithms sorting sample-sort distribution
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Multiway Merge Sort

Merge sort variant that merges more than two sorted sequences at each step.
algorithms sorting merge-sort multiway-merge
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Tournament Merge Sort

Merge-based sorting algorithm that uses a tournament tree to repeatedly select the next smallest element.
algorithms sorting merge-sort tournament-tree