Sorting in Average Time $o(\log \,n)$

DOI10.1137/0402024zbMath0673.68041OpenAlexW1999670727MaRDI QIDQ3827548

János Komlós, Miklós Ajtai, Endre Szemerédi, Dino Karabeg

Publication date: 1989

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0402024

zbMATH Keywords

sortingparallel algorithmsaverage-time complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Parallel numerical computation (65Y05)

Related Items

Time lower bounds for parallel sorting on a mesh-connected processor array, Geometric p-Center Problems with Centers Constrained to Two Lines, An introduction to randomized algorithms, Linear-Time Fitting of a k-Step Function, Oblivious Parallel RAM and Applications, Improved upper bounds on Shellsort