title: Can you do a parallel counting sort in O(n/p) time?
body: <p>Is is possible to do a counting sort in parallel and achieve O(n/p) runtime?</p>
  
  <p>Take an example where we have an array with millions of elements that range from 1-10. A merge sort will run in no better than O(nlogn) time. A counting sort applied to this problem will run in O(n) time. Parallelizing a counting sort could be interesting. If we assign a subarray with n/p elements to each processor and each processor has its own count array of size 9, the initial step where element counts are accumulated should take O(n/p) time. Consolidating all the count arrays into a single array should take O(p) time as you are only iterating p count arrays, each a constant size. </p>
  
  <p>I haven't been able to fully think through the last step in the counting sort where the elements are placed in order. If the elements of the count array are atomic, you could assign n/p sections of the original array to individual processors and achieve some parallelization, but there would be contention at individual elements of the count array, potentially substantially reducing parallelization. If the input array is all 10's, all processors would serialize on the 9th element of the count array, reducing algorithmic efficiency to O(n). </p>
  
  <p>You could assign subarrays of the count array to each of p processors and you are back to O(n/p) runtime, but only if the elements are distributed fairly evenly. And, in our example, you would be limited to 10 processors. If the elements are not distributed evenly, one or more processors could be doing a larger proportion of the work. For instance, if half of the elements in the input array are 10, one processor would have to step through half the array. Worst case, the array is all 10's and a single processor would have to step through the entire array devolving runtime to O(n). </p>
  
  <p>Maybe you could divide individual elements of the count array among multiple processors. For instance, if there are 50 10's in the input array, element 9 of the count array would reflect this. You could have 5 processors write 10 10's each to the proper positions in the output array. This again devolves to O(n) runtime if there are fewer than p elements at each index location of the count array, but it avoids the problem where distribution of element values is uneven.</p>
  
  <p>Is it possible to do a counting sort in O(n/p) time?</p>