High-throughput sorting: parallel merge and quicksort, GPU bitonic and radix sort, SIMD sorting networks, and distributed partition-based sorts.
| index | slug | name |
|---|---|---|
| 311 | parallel-merge-sort | Parallel Merge Sort |
| 312 | parallel-quicksort | Parallel Quicksort |
| 313 | parallel-sample-sort | Parallel Sample Sort |
| 314 | parallel-radix-sort | Parallel Radix Sort |
| 315 | parallel-bitonic-sort | Parallel Bitonic Sort |
| 316 | parallel-odd-even-sort | Parallel Odd Even Sort |
| 317 | parallel-counting-sort | Parallel Counting Sort |
| 318 | gpu-bitonic-sort | GPU Bitonic Sort |
| 319 | gpu-radix-sort | GPU Radix Sort |
| 320 | gpu-merge-sort | GPU Merge Sort |
| 321 | gpu-sample-sort | GPU Sample Sort |
| 322 | cuda-warp-sort | CUDA Warp Sort |
| 323 | cuda-block-sort | CUDA Block Sort |
| 324 | simd-bitonic-sort | SIMD Bitonic Sort |
| 325 | simd-sorting-network | SIMD Sorting Network |
| 326 | bitonic-sorting-network | Bitonic Sorting Network |
| 327 | odd-even-sorting-network | Odd Even Sorting Network |
| 328 | bitonic-merge-network | Bitonic Merge Network |
| 329 | mapreduce-sort | MapReduce Sort |
| 330 | terasort | TeraSort |
| 331 | distributed-sample-sort | Distributed Sample Sort |
| 332 | distributed-range-partition-sort | Distributed Range Partition Sort |
| 333 | psrs | Parallel Sorting by Regular Sampling |
| 334 | bitonic-sort-on-hypercube | Bitonic Sort on Hypercube |
| 335 | shear-sort | Shear Sort |
Parallel Merge SortDivide the input, sort subarrays in parallel, then merge them using parallel merge procedures.
Parallel QuicksortPartition the array around a pivot, then sort partitions concurrently using parallel recursion.
Parallel Sample SortChoose splitters from samples, partition the input into buckets, sort buckets independently, then concatenate the sorted buckets.
Parallel Radix SortSort integer keys by processing fixed width digit groups in parallel using counting and prefix sums.
Parallel Bitonic SortSort data by building and merging bitonic sequences through a regular compare and exchange network.
Parallel Odd Even SortSort an array by repeatedly comparing odd indexed and even indexed adjacent pairs in parallel.
Parallel Counting SortCount key frequencies in parallel, compute prefix sums, then scatter elements into sorted positions.
GPU Bitonic SortSort data on a GPU using a regular bitonic compare and exchange network.
GPU Radix SortSort fixed width keys on a GPU using digit passes, parallel histograms, prefix sums, and scatter operations.
GPU Merge SortSort data on a GPU by recursively merging sorted runs using parallel merge primitives.
GPU Sample SortSort data on a GPU by selecting splitters, partitioning into buckets in parallel, then sorting buckets independently.
CUDA Warp SortSort a small set of values inside one CUDA warp using shuffle operations and compare exchange steps.
CUDA Block SortSort a block sized tile on the GPU using shared memory and cooperative threads.
SIMD Bitonic SortSort small vectors using SIMD registers with a fixed bitonic compare exchange network.
SIMD Sorting NetworkSort a fixed size vector by mapping a data independent sorting network to SIMD compare, shuffle, and blend operations.
Bitonic Sorting NetworkSort a fixed size sequence with a bitonic compare and exchange network whose schedule is independent of input values.
Odd Even Sorting NetworkSort a fixed size sequence using a data independent network of odd even compare exchange stages.
Bitonic Merge NetworkMerge a bitonic sequence into a sorted sequence using a fixed comparator network.
MapReduce SortSort large distributed datasets by partitioning records by key range, sorting partitions locally, and writing ordered output shards.
TeraSortSort very large datasets with range partitioning, distributed shuffle, and reducer local sorting.
Distributed Sample SortSort data across machines by sampling keys, choosing splitters, redistributing records into ordered buckets, and sorting buckets locally.
Distributed Range Partition SortSort distributed data by assigning fixed key ranges to workers, routing records by range, then sorting locally.
PSRSSort data in parallel by local sorting, regular sampling, global splitter selection, redistribution, and final local merge.
Bitonic Sort on HypercubeSort distributed keys across hypercube processors using dimension based compare and exchange stages.
Shear SortSort a two dimensional mesh by alternating row sorts and column sorts until the grid is globally ordered.