15
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ This is out-of-date information, but the 1995 paper "Lower bounds for sorting networks" (Kahale et al.) established a lowerbound constant of 3.27, but at that time the authors said that the upperbound constants in the AKS network "remain impractically large." (AKS = Ajtai, Komlós, Szemerédi). $\endgroup$
    – Joseph O'Rourke
    Mar 25, 2012 at 17:40
  • 1
    $\begingroup$ I have no useful reference for you, but perhaps this idea might work. (Also, you could ask Bjorn Poonen directly.) In trying to analyze Combsort I came across some papers dealing with sorting algorithms as well as sorting networks. I asked this question mathoverflow.net/questions/31364/… , and have received not much. One thing I did not do which you might do is to take the papers there (or others), use a citation index on them, and see if anything has popped up in the last few years. Gerhard "Tell Me What You Find" Paseman, 2012.03.25 $\endgroup$
    – Gerhard Paseman
    Mar 26, 2012 at 4:42
  • 1
    $\begingroup$ On an aside, you might be interested in the conclusions of this recent paper on optimal sorting networks: arxiv.org/abs/1310.6271 $\endgroup$
    – Suvrit
    Oct 25, 2013 at 21:15

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.