tag

#gpu

7 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 ›

GPU Merge Sort

GPU Merge Sort GPU merge sort adapts merge sort to GPU execution by replacing recursive merging with parallel merge kernels. The algorithm operates in passes, merging sorted runs of increasing size. Unlike GPU radix sort, this method works for arbitrary comparable keys. Its performance depends on efficient parallel merge and memory throughput. Problem Given an array $A$ of size $n$ stored on a GPU, sort it in nondecreasing order. Algorithm...
algorithms sorting gpu merge-sort
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

CUDA Block Sort

CUDA Block Sort CUDA block sort sorts a tile of data using all threads in a block. It extends warp level sorting to larger sizes by using shared memory and synchronization within a thread block. Each block loads a chunk of the array into shared memory, sorts it cooperatively, then writes it back. This is often used as a building block for full GPU sorting algorithms such as merge sort...
algorithms sorting gpu cuda block-sort
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

GPU Radix Sort

GPU Radix Sort GPU radix sort sorts fixed width integer keys by processing a small number of bits at a time. Each pass groups keys by the current digit. On GPUs, the main work is building histograms, computing prefix sums, and scattering keys into their next positions. For integer keys, GPU radix sort is often one of the fastest general sorting methods because it avoids comparisons and exposes large amounts...
algorithms sorting gpu radix-sort
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

CUDA Warp Sort

CUDA Warp Sort CUDA warp sort sorts a small group of values within one warp. A warp is a fixed group of GPU threads that execute together. On NVIDIA GPUs, a warp commonly contains 32 lanes. The algorithm is usually implemented with compare and exchange steps using warp shuffle instructions. Since all lanes execute the same instruction stream, warp sort works best with regular sorting networks such as bitonic sort...
algorithms sorting gpu cuda warp
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

GPU Bitonic Sort

GPU Bitonic Sort GPU bitonic sort is a GPU implementation of bitonic sort. It uses a fixed compare and exchange pattern that fits SIMD style execution well. The algorithm performs more comparisons than quicksort or merge sort, but its memory access and control flow are regular. This makes it useful for small to medium arrays, block local sorting, graphics workloads, and GPU kernels where predictable execution is more important than...
algorithms sorting gpu bitonic-sort
Wiki › Algorithms › 01. Searching and Sorting › 11. Parallel, Distributed, and GPU Sorting ›

GPU Sample Sort

GPU Sample Sort GPU sample sort partitions the input into buckets using sampled splitters, then sorts each bucket independently on the GPU. It is a distribution based algorithm similar to parallel sample sort, adapted to GPU execution with attention to memory coalescing and load balancing. This method scales well for large inputs because most work after partitioning becomes independent across buckets. Problem Given an array $A$ of size $n$ on...
algorithms sorting gpu sample-sort