是否可以并行对几乎排序的数组进行排序？

问：

“几乎排序的数组”在这里被定义为每个元素在排序数组中距离其位置最多。数组大小为 。串行中的基本算法是使用最小堆（假设您要按升序排序），它给出 O（（n-k）log k + k） 运行时间，或者，您可以使用插入排序并获得 O（nk） 运行时间。kn

对于这两种算法中的任何一种，我都没有看到并行化它的好方法。因此，您可以将数组拆分为连续的块，并将每个段发送到单个线程，但问题是段末尾的某些元素总是会落入排序数组中的不同段。因此，如果您要使用多线程，则会遇到数据争用问题，或者，您可以添加锁以避免数据争用问题，但会牺牲性能。

有没有更好的方法可以并行解决这个问题？