tag

#samplesort

2 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

IPS4o

IPS4o IPS4o stands for in-place parallel super scalar samplesort. It is a high performance comparison sorting algorithm designed for modern multicore CPUs. It combines samplesort partitioning, cache efficient block movement, and parallel execution while keeping extra memory usage small. The algorithm is useful when comparison sorting is required but ordinary quicksort or mergesort does not make full use of hardware parallelism. Problem Given an array $A$ of $n$ comparable elements,...

Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Adaptive Samplesort

Adaptive Samplesort Adaptive samplesort is a samplesort variant that chooses splitters from the input and adjusts partitioning to the observed distribution. It is useful when the input has skew, duplicates, or uneven key ranges. You use it when ordinary quicksort or fixed bucket sorting may create badly imbalanced partitions. Problem Given an array ( A ) of length ( n ), sort it by dividing values into buckets whose boundaries...