tag

#parallel

13 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
Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.22 Parallel Sorting

6.22 Parallel Sorting Parallel sorting distributes work across multiple processing units. The goal is to reduce wall-clock time while preserving correctness and scalability. The cost model includes total work, parallel time (span), communication, and synchronization. Problem You have an array A[0..n-1] and p processors. You want to sort faster than a single-threaded algorithm by exploiting parallelism. Models Two common models guide design: Shared-memory model: threads access a common address space...
algorithms sorting parallel concurrency May 4, 2026
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

Parallel Odd Even Sort

Parallel Odd Even Sort Parallel odd even sort is the parallel form of odd even transposition sort. It works like bubble sort, but splits adjacent comparisons into two independent phases. One phase compares pairs starting at even indices, and the other compares pairs starting at odd indices. Because pairs in the same phase do not overlap, all comparisons in one phase can run at the same time. Problem Given an...
algorithms sorting parallel odd-even-sort
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

Parallel Sample Sort

Parallel Sample Sort Parallel sample sort is a parallel sorting algorithm based on partitioning by sampled splitters. It first chooses representative keys from the input, uses them to divide the data into buckets, sorts each bucket independently, then concatenates the buckets in order. The method is useful when many processors are available because most work after partitioning is independent. Its quality depends on how well the samples represent the input...
algorithms sorting parallel sample-sort
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

Shear Sort

Shear Sort Shear sort is a parallel sorting algorithm for data arranged on a two dimensional mesh. It alternates between sorting rows and sorting columns. Rows are sorted in a snake like order: even rows left to right, odd rows right to left. Columns are sorted top to bottom. This alternating pattern gradually moves small values toward the beginning of the snake order and large values toward the end. Problem...
algorithms sorting parallel mesh shear-sort
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

Parallel Quicksort

Parallel Quicksort Parallel quicksort follows the same partition based divide and conquer structure as quicksort, but executes recursive calls concurrently. The key idea is that once the partition step finishes, the left and right subarrays become independent and can be processed in parallel. Compared to parallel merge sort, this method avoids the cost of merging but introduces challenges in load balancing and pivot quality. Problem Given an array $A$ of...
algorithms sorting parallel quicksort
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

Parallel Radix Sort

Parallel Radix Sort Parallel radix sort sorts fixed width keys by processing one digit group at a time. A digit group may be a byte, a few bits, or another small radix unit. Each pass groups elements by the current digit while preserving the order needed by the radix variant. For integer keys, parallel radix sort is often faster than comparison sorting because it uses key digits directly. Its main...
algorithms sorting parallel radix-sort
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

Parallel Counting Sort

Parallel Counting Sort Parallel counting sort extends counting sort by distributing counting and placement across multiple workers. It assumes keys are integers within a bounded range. Instead of comparing elements, it counts occurrences and reconstructs the sorted output. The algorithm consists of three main stages: local counting, prefix sum computation, and parallel scatter. Problem Given an array $A$ of size $n$ with integer keys in range $[0, k)$, produce a...
algorithms sorting parallel counting-sort
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

PSRS

Parallel Sorting by Regular Sampling (PSRS) PSRS is a structured parallel sorting algorithm designed for shared memory or distributed systems. It combines local sorting, deterministic sampling, and balanced redistribution. Unlike naive sample sort, PSRS uses regular sampling to guarantee better load balance without heavy randomness. Problem Given $n$ elements distributed across $p$ processors, sort them in nondecreasing order. Each processor initially holds about $n/p$ elements. Algorithm PSRS proceeds in five...
algorithms sorting parallel psrs
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Parallel External Merge Sort

Parallel External Merge Sort Parallel external merge sort extends external merge sort by using multiple processors, threads, and storage devices to increase throughput. It parallelizes both run generation and merging while keeping I/O mostly sequential. The algorithm is used in large-scale systems where sorting terabytes of data requires distributing work across CPUs and disks. Problem Given a dataset much larger than memory, sort it efficiently using multiple processors and parallel...
algorithms sorting external-memory parallel
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

Parallel Bitonic Sort

Parallel Bitonic Sort Parallel bitonic sort is a sorting network based algorithm. It sorts by repeatedly forming bitonic sequences and then merging them into sorted order. A bitonic sequence first increases and then decreases, or can be rotated into that shape. The algorithm works especially well on parallel hardware because the compare and exchange pattern is regular and independent of the input values. Problem Given an array $A$ of size...
algorithms sorting parallel bitonic-sort
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

Parallel Merge Sort

Parallel Merge Sort Parallel merge sort extends merge sort by executing recursive subproblems concurrently. The structure remains divide and conquer, but the recursion tree becomes a parallel computation graph. You split the array into halves, sort each half in parallel, then merge the results. The merge step can also be parallelized using partitioning techniques. Problem Given an array $A$ of size $n$, produce a sorted array in nondecreasing order using...
algorithms sorting parallel merge-sort
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