Parallel Shear Sort

Manuel Eberl 📧 and Peter Lammich 📧

September 17, 2024

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.

Abstract

This entry provides a formalisation of parallel shear sort, a comparison-based sorting algorithm intended for highly parallel systems. It sorts $n$ elements in $O(\log n)$ steps, each of which involves sorting $\sqrt{n}$ independent lists of $\sqrt{n}$ elements each.

If these smaller sort operations are done in parallel with a conventional $O(n\log n)$ sorting algorithm, this leads to an overall work of $O(n \log^2(n))$ and a span of $O(\sqrt{n}\log^2(n))$ -- a considerable improvement over conventional non-parallel sorting.

License

BSD License

Topics

Session Parallel_Shear_Sort