Sorting in rounds
type: Item
instance of: scholarly article
title: Sorting in rounds
zbMATH Open document ID: 0667.68075
DOI: 10.1016/0012-365X(88)90190-2
author: Béla Bollobás
published in: Discrete Mathematics
publication date: 1988-01-01T00:00:00Z
review text: The paper considers the number SORT(n,r) of parallel processors necessary to sort n elements in time r, in the case where \(r=r(n)\) is small compared to n. The author establishes an asymptotic upper bound \[ f(n,r):=2^{r+1} n^{1+1/r} (\log n)^{2-2/r} (\log \log n)^{-(r- 1)/r} \] for \(2\leq r(n)\leq \log \log \log n\). (Results by Ajtai et a. imply an upper bound SORT(n,r)\(\leq c n (\log n)/r\) for \(r\geq \log n)\). The probabilistic method is used to show the existence of an algorithm and explicit constructions of the graphs or estimates on the order of magnitude of the constants involved are not given. However, the author observes that the sorting networks only depend on n and r, and of course are independent of the ordering of the input.
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4092790
zbMATH Keywords: parallel processing
zbMATH Keywords: probabilistic method
zbMATH Keywords: sorting networks
MaRDI profile type: Publication
cites work: Sorting in \(c \log n\) parallel steps
cites work: Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
cites work: Q3682518
cites work: Graphs whose every transitive orientation contains almost every relation
cites work: Q3702524
cites work: Sorting in one round
cites work: Parallel sorting
cites work: Q3922725
cites work: Parallel Sorting with Constant Time for Comparisons
cites work: Sorting and Merging in Rounds
cites work: Ramanujan graphs
cites work: Hecke operators and distributing points on the sphere I
description: scientific article; zbMATH DE number 4092790