[Omp] Parallel sort

[Michael Suess]

On Tuesday 21 March 2006 19:01, Francisco Jesús Martínez Serrano wrote:
> Hello.
>
> We need an efficient parallel sort implementation for our OpenMP
> application.
>
> I've been searching, and a nice algorithm seems to be Shi & Schaeffer's
> Parallel Sorting by Regular Sampling(PSRS). However i didn't manage to find
> a treaded implementation of the algorithm (neither any other parallel
> sorting
> algorithm). I can only find old implementations for machines like SP2, TD3,
> CM5 and so on. Some of them in specific languages like Simple-C.
>
> I've found a more modern one, but it's a MPI implementation.
>
> Does anybody know if there's a free implementation (maybe NAG or IMSL
> have what we want, but we don't have them) of a threaded parallel
> algorithm?
>
> Is there any possibility of linking against a MPI-shmem library performing
> the algorithm?

Hi Francisco,

since nobody else seems to step up and has an idea, I have experimented with 
quicksort in OpenMP in the past. You can find the paper about it here:
http://www.plm.eecs.uni-kassel.de/plm/fileadmin/pm/publications/suess/sortOpenMP.pdf

But keep in mind, that the goal of this work was not to find the fastest 
parallel sorting algorithm of all times! The speedups are nevertheless ok (my 
humble opinion). The programs are available under the GPL in the OMP Source 
code repository (which seems to be down at the moment, but I can mail them to 
you if needed). If you have problems with GPL'd programs, I am sure we can 
figure something out.

Best regards,
Michael Suess