Sorting in Average Time $o(\log \,n)$
From MaRDI portal
Publication:3827548
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
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