Logarithmic time cost optimal parallel sorting is not yet fast in practice

When looking for new and faster parallel sorting algorithms for use in massively parallel systems it is tempting to investigate promising alternatives from the large body of research doneon parallel sorting in the eld of theoretical computer science. Such \\theoretical " algorithms are mainly described for the PRAM (Parallel Random Access Machine) model of computation [13, 26]. This paper shows how this kind of investigation can be done on a simple but versatile environment forprogramming and measuring of PRAM algorithms [18, 19]. The practical value of Cole's Parallel Merge Sort algorithm [10,11] have beeninvestigated by comparing it with Batcher's bitonic sorting [5]. The O(log n) time consumption of Cole's algorithm implies that it must be faster than bitonic sorting which is O(log 2 n) time|if n is large enough. However, we havefound that bitonic sorting is faster as long as n is less than 1:2 1021, i.e. more than 1 Giga Tera items!. Consequently, Cole's logarithmic time algorithm is not fast in practice. 1Introduction and Motivation The work reported in this paper is an attempt to lessen the gap between theory and practice within the eld of parallel computing. Within theoretical computer science, parallel algorithms are mainly compared by using asymptotical analysis (O-notation). This paper gives an example on how the analysis of implemented algorithms on nite problems provides new and more practically oriented results than those traditionally obtained by asymptotical analysis. Parallel Complexity Theory|A Rich Source for