tag

#sample-sort

6 pages tagged

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 ›

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
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Integer Sample Sort

Integer Sample Sort Integer sample sort is a specialization of sample sort for integer keys. It selects sample elements to estimate the distribution, chooses splitters, and partitions the array into buckets. Each bucket is then sorted recursively or with a suitable subroutine. Because keys are integers, classification can use arithmetic or bit operations, and buckets can be balanced more precisely than in general comparison sorting. Problem Given an array $A$...
algorithms sorting sample-sort integer-sorting
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 › 10. External Memory, Cache, and Database Sorting ›

External Sample Sort

External Sample Sort External sample sort is a distribution-based external sorting algorithm. It selects a sample of the input to determine splitters, partitions the data into balanced buckets using those splitters, and then sorts each bucket independently. The method reduces the number of merge passes by ensuring that buckets are roughly equal in size. Problem Given a large dataset that does not fit in memory, sort it efficiently while minimizing...
algorithms sorting external-memory sample-sort
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Sample Sort

Sample Sort Sample sort is a generalization of quicksort and bucket sort. It selects a sample of elements, uses them to define partition boundaries, and distributes the data into multiple buckets that are sorted independently. It is widely used in parallel and distributed systems because it produces well balanced partitions. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots \le A[n-1]...
algorithms sorting sample-sort distribution