Abstract

This entry in the Archive of Formal Proofs 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(n)²) and a span of O(sqrt(n) log(n)²) – a considerable improvement over conventional non-parallel sorting.

BibTeX

@article{Parallel_Shear_Sort-AFP,
  author  = {Manuel Eberl and Peter Lammich},
  title   = {Parallel Shear Sort},
  journal = {Archive of Formal Proofs},
  month   = {September},
  year    = {2024},
  note    = {\url{https://isa-afp.org/entries/Parallel_Shear_Sort.html},
             Formal proof development},
  ISSN    = {2150-914x},
}