Sorting in Average Time $o(\log \,n)$
Miklós Ajtai, D. Karabeg, János Komlós, Endre Szemerédi · SIAM Journal on Discrete Mathematics · 1989
This paper presents a comparison sorting algorithm for the abstract CROW PRAM parallel computer model. The algorithm sorts n input values using n processors and runs in time $O(\log n/\log \log n)$ on the average, assuming that all permutations of the input are equally likely.