Editing Radix sort (section)

===Application to parallel computing===
This recursive sorting algorithm has particular application to [[parallel computing]], as each of the bins can be sorted independently. In this case, each bin is passed to the next available processor. A single processor would be used at the start (the most significant digit). By the second or third digit, all available processors would likely be engaged. Ideally, as each subdivision is fully sorted, fewer and fewer processors would be utilized. In the worst case, all of the keys will be identical or nearly identical to each other, with the result that there will be little to no advantage to using parallel computing to sort the keys.

In the top level of recursion, opportunity for parallelism is in the [[counting sort]] portion of the algorithm. Counting is highly parallel, amenable to the parallel_reduce pattern, and splits the work well across multiple cores until reaching memory bandwidth limit. This portion of the algorithm has data-independent parallelism. Processing each bin in subsequent recursion levels is data-dependent, however. For example, if all keys were of the same value, then there would be only a single bin with any elements in it, and no parallelism would be available. For random inputs all bins would be near equally populated and a large amount of parallelism opportunity would be available.<ref>{{Cite web|url=http://www.drdobbs.com/parallel/parallel-in-place-n-bit-radix-sort/226600004|title=Parallel In-Place N-bit-Radix Sort|first=Victor J.|last=Duvanenko|website=Dr. Dobb's}}</ref>

There are faster parallel sorting algorithms available, for example optimal complexity O(log(''n'')) are those of the Three Hungarians and Richard Cole<ref>A. Gibbons and [[Wojciech Rytter|W. Rytter]], ''Efficient Parallel Algorithms''. Cambridge University Press, 1988.</ref><ref>H. Casanova et al, ''Parallel Algorithms''. Chapman & Hall, 2008.</ref> and [[Ken Batcher|Batcher]]'s [[Bitonic sorter|bitonic merge sort]] has an algorithmic complexity of O(log<sup>2</sup>(''n'')), all of which have a lower algorithmic time complexity to radix sort on a CREW-[[Parallel random-access machine|PRAM]]. The fastest known PRAM sorts were described in 1991 by [[David M W Powers]] with a parallelized quicksort that can operate in O(log(n)) time on a CRCW-PRAM with ''n'' processors by performing partitioning implicitly, as well as a radixsort that operates using the same trick in O(''k''), where ''k'' is the maximum keylength.<ref>David M. W. Powers, [https://sites.cs.ucsb.edu/~gilbert/cs140/old/cs140Win2009/sortproject/ParallelQuicksort.pdf Parallelized Quicksort and Radixsort with Optimal Speedup], ''Proceedings of International Conference on Parallel Computing Technologies''. [[Novosibirsk]]. 1991.</ref> However, neither the PRAM architecture or a single sequential processor can actually be built in a way that will scale without the number of constant [[fan-out]] gate delays per cycle increasing as O(log(''n'')), so that in effect a pipelined version of Batcher's bitonic mergesort and the O(log(''n'')) PRAM sorts are all O(log<sup>2</sup>(''n'')) in terms of clock cycles, with Powers acknowledging that Batcher's would have lower constant in terms of gate delays than his Parallel [[quicksort]] and radix sort, or Cole's [[merge sort]], for a keylength-independent [[sorting network]] of O(nlog<sup>2</sup>(''n'')).<ref>David M. W. Powers, [http://david.wardpowers.info/Research/AI/papers/199501-ACAW-PUPC.pdf Parallel Unification: Practical Complexity], Australasian Computer Architecture Workshop, Flinders University, January 1995</ref>