Histogramming based large scale parallel sorting algorithm

We design a new large scale parallel sorting algorithm that combines sampling and histogramming. We prove sound guarantees about the algorithm and also show that it is essentially optimal in a sense. We implement it in a highly parallel astronomical application and show runtime benefits from our algorithm.

• Optimal Round and Sample-Size Complexity for Partitioning in Parallel Sorting
Wentao Yang*, Vipul Harsh*, Edgar Solomonik.
Symposium on Parallelism in Algorithms and Architectures (SPAA), June 2023.


• Histogram Sort with Sampling (slides, code)
Vipul Harsh, Laxmikant Kale, Edgar Solomonik.
Symposium on Parallelism in Algorithms and Architectures (SPAA), June 2019.


• Histogram Sort with Sampling
Vipul Harsh
M.S. thesis, May 2017.