Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
there seem to exist papers on parallel sorting, but I have not found a good introduction into this topic.
So, do you know a good summary or introduction into parallel sorting algorithms? In particular, I am looking for some good and handy examples that realize best lower bounds (e.g. like merge sort in the sequentiel case.), if available.
Parallel algorithms are very dependent on the computation model, and there are a lot of different parallel models. So, it is difficult to have a representative general introduction.
I teach parallel algorithms following the pattern I first saw in a similar course by my PhD advisor. I spend the first few lectures on sorting networks, covering Batcher's constructions, and AKS very briefly. Then I introduce a specific general-purpose parallel computation model (BSP suits me very well), and cover five or six textbook-type algorithmic problems, first recalling their sequential algorithms, and then discussing with students how to parallelize them efficiently.
Sorting is one of these problems. Its BSP solution is very elegant: parallel sorting by regular sampling (presented in the original paper by Shi and Schaeffer, and also Quinn's book "Parallel Computing"). It does realise the relevant lower bounds in computation, communication and, surprisingly, also synchronisation - by synchronising the whole computation only a constant number of times (whereas looking at mergesort and AKS, one would expect to have to synchronize O(log n) times). The optimality proof is non-trivial, yet simple enough to be presented in an undergraduate class in 20 minutes - so for me, it is indeed a very good and handy example to teach.
Another good example is Leighton's columnsort - I am not teaching it, but would be if I had a bit more time.
