Parallel Shear Sort

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.