I recently found myself talking about Szemerédi's mathematics, and briefly discussed his famous sorting network, discovered with Ajtai and Komlós. Apparently their algorithm is not practical because it takes time $C\log n$ for a fairly large constant $C$, and so in practice it is better to go for an algorithm that takes time, say, $2(\log n)^2$. I have read that reducing this constant is still an interesting open problem, and wondered if there was a good place to find out what the status of this problem is.

The answer may depend on exactly what is required of the algorithm, so let me ask a precise question, though I may be interested in answers to slightly different but related questions. Let's suppose you have $n=2m$ objects to sort, and you want to minimize the number of rounds. In each round you can partition the $n$ objects into $m$ pairs and compare each pair, and in between rounds you can do whatever computations you want. [See below -- I've changed my mind about that last point.] The number of rounds you need is of the form $C\log n$, but what is known about the constant $C$?

If I understand correctly, the question I've just asked isn't the usual one, since usually one requires more. The idea is that you start with the objects lined up from left to right in an arbitrary order, and then at each round you choose some way of partitioning the objects into pairs, but in between rounds the only thing you can do is switch the objects in each pair if the larger one is to the left of the smaller. Also, the comparisons you do in each round are, I think, independent of the results of previous rounds. This is called a *sorting network*.

One other way in which one can vary the question is according to whether you allow randomized algorithms. The case that interests me most is the one where randomness is allowed and so is any amount of computation between rounds. Actually, I now realize that that's a bit too generous, since it means that we can check every single ordering and see whether it is consistent with the comparisons we have made. So I'd better change what I'm asking. First, what is known about the constant $C$ in the best sorting network, with randomness allowed? Secondly, is the best known constant smaller if you allow "reasonable" additional computations to take place between rounds?