tag

#parallel-sorting

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 › 12. Specialized Search and Sorted-Order Procedures ›

Merge Path Search

Merge Path Search Merge path search finds partition points in two sorted arrays so that a merge can be split into independent chunks. It is mainly used for parallel merge, GPU merge, and distributed sorted data processing. The method views merging as a path through a grid. Each step consumes one element from either the first array or the second array. A diagonal in this grid represents a fixed number...