是否有可能并行执行计数排序并实现O(n/p)运行时间?
举一个例子，我们有一个包含数百万个元素的数组，这些元素的范围从1到10。归并排序的运行时间不会超过0 (nlogn)。应用于此问题的计数排序将在O(n)时间内运行。并行化计数排序可能很有趣。如果我们为每个处理器分配一个包含n/p个元素的子数组，并且每个处理器都有自己的大小为9的计数数组，那么累积元素计数的初始步骤应该花费O(n/p)时间。将所有count数组合并为单个数组应该花费O(p)时间，因为您只迭代p个count数组，每个数组的大小都是恒定的。
我还没能完全思考完计数排序的最后一步，其中元素按顺序排列。如果count数组的元素是原子的，则可以将原始数组的n/p段分配给各个处理器并实现一些并行化，但是在count数组的各个元素上会存在争用，这可能会大大降低并行化。如果输入数组都是10，那么所有处理器都将在count数组的第9个元素上进行序列化，从而将算法效率降低到0 (n)。
您可以将count数组的子数组分配给p个处理器中的每个处理器，并且您将返回O(n/p)运行时间，但前提是元素分布相当均匀。在我们的示例中，您将被限制为10个处理器。如果元素分布不均匀，则一个或多个处理器可能会承担较大比例的工作。例如，如果输入数组中有一半的元素是10，那么一个处理器就必须遍历一半的数组。最坏的情况是，数组都是10，单个处理器必须遍历整个数组，将运行时间缩短到0 (n)。
也许您可以将count数组的单个元素分配给多个处理器。例如，如果输入数组中有50个10,count数组的元素9将反映这一点。您可以让5个处理器分别将10个10写入输出数组中的适当位置。如果count数组的每个索引位置上的元素少于p个，这同样需要O(n)运行时间，但它避免了元素值分布不均匀的问题。
是否有可能在O(n/p)时间内完成计数排序?
是有可能的。将数组分成等长的p部分。然后为每个进程创建一个计数数组'c'。让每个进程计算元素的数量并将它们存储在c中。这需要O(n/p)。现在将所有计数数组c加在一起，并将该数组共享给所有进程。这将取O(p*b)，其中b是可能值的数量。到目前为止，这正是你的方法。现在您可以在p进程中重新创建数组，因为您可以计算c中值的第一个和最后一个索引。对于每个值i，它的第一个索引是c中前面所有值的和。最后一个索引是第一个索引加上c[i]。这个计算可以在O(i)中完成，其中i比b小，所以它比O(b)小。每个进程现在可以重新填充自己的部分。这再次需要O(n/p)。总而言之，你有n/p + p*b + b + n/p。如果是p*b << n，就会得到O(2*n/p)。(因为2/p是一个常数因子，所以仍然有O(n)类。但是并行化将显著加快你的算法)