tag

#distributed

6 pages tagged

Wiki › Algorithms › 01. Searching and Sorting ›

11. Parallel, Distributed, and GPU Sorting

11. Parallel, distributed, and GPU sorting, 25 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...
algorithms sorting parallel gpu distributed May 6, 2026
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

Distributed Sample Sort

Distributed Sample Sort Distributed sample sort sorts a dataset spread across multiple machines. It uses sampled keys to choose global splitters. These splitters divide the key space into ordered buckets. Each machine sends records to the bucket owner, each bucket is sorted locally, and the sorted buckets form the final output. The main purpose of sampling is load balance. Good splitters make every worker receive roughly the same amount of...
algorithms sorting distributed sample-sort
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

TeraSort

TeraSort TeraSort is a benchmark style distributed sorting procedure for very large datasets. It is commonly associated with sorting one terabyte or more of records using a cluster. The core idea is simple: sample keys, choose range partitions, shuffle records to the correct partitions, sort each partition locally, and write ordered output shards. TeraSort is close to MapReduce sort in structure, but it is usually discussed as a performance benchmark....
algorithms sorting distributed terasort
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

Distributed Range Partition Sort

Distributed Range Partition Sort Distributed range partition sort divides the key space into fixed ranges and assigns each range to a worker. Each worker sends records to the correct range owner, then sorts its received records locally. This method is simpler than sample sort because it uses predefined ranges. It works well when the key distribution is known or bounded. Problem Given $n$ records distributed across $p$ workers, sort all...
algorithms sorting distributed range-partition
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

MapReduce Sort

MapReduce Sort MapReduce sort sorts a large dataset across many machines using the MapReduce execution model. The input is split into blocks, mapper tasks emit key value records, the shuffle phase partitions records by key range, and reducer tasks sort their assigned partitions. The result is a set of sorted output shards. If partition boundaries are chosen correctly, concatenating reducer outputs in partition order gives one globally sorted sequence. Problem...
algorithms sorting distributed mapreduce
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

Bitonic Sort on Hypercube

Bitonic Sort on Hypercube Bitonic sort on a hypercube maps the bitonic sorting network onto processors connected as a hypercube. Each processor communicates with neighbors that differ in one binary address bit. The fixed communication pattern matches the regular compare and exchange stages of bitonic sort. This model is useful for parallel sorting theory and for systems whose communication topology resembles a hypercube. Problem Given $n$ keys distributed across $p...
algorithms sorting parallel distributed hypercube bitonic-sort