tag

#partitioning

2 pages tagged

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

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