有什么算法值得对链表进行并行排序吗？

众所周知，合并排序是用于对链表进行排序的最佳算法。

大多数合并排序是根据数组进行解释的，每个合并都将递归排序。这使得并行化变得微不足道：分别对每个半部分进行排序，然后将两个半部分合并。

但是，链表中没有“中途”点；链表直到结束：

头→[a]→[b]→[c]→[d]→[e]→[f]→[g]→[h]→[i]→[j]→...

我现在执行的实现一次遍历列表以获取计数，然后递归拆分计数，直到我们将节点与其进行比较NextNode。递归会记住两个半部分在哪里。

这意味着链接列表的MergeSort在列表中线性进行。由于它似乎要求线性地通过列表，因此我认为它不能并行化。我能想象的唯一方法是：

• 遍历清单以计数 O(n)
• 走一半的清单到中途点 O(n/2)
• 然后将每一半分类 O(n log n)

但是，即使我们确实在单独的线程中对排序（a，b）和（c，d）进行NextNode了并行处理，我仍认为重新排序期间的错误共享会杀死并行处理的任何优点。

是否有用于对链表进行排序的并行算法？

数组合并排序算法

这是对数组执行合并排序的标准算法：

algorithm Merge-Sort
    input:
        an array, A (the values to be sorted)
        an integer, p (the lower bound of the values to be sorted)
        an integer, r (the upper bound of the values to be sorted)

    define variables:
        an integer, q (the midpoint of the values to be sorted)

    q ← ⌊(p+r)/2⌋
    Merge-Sort(A, p, q)   //sort the lower half
    Merge-Sort(A, q+1, r) //sort the upper half   
    Merge(A, p, q, r)     

此算法是为具有任意索引访问权限的数组设计的，其含义是。为了使其适合链接列表，必须对其进行修改。

链表合并排序算法

这是（单线程）单链接列表，合并排序，算法，我目前使用该算法对单链接列表进行排序。它来自Gonnet + Baeza Yates算法手册

algorithm sort:
    input:
        a reference to a list, r (pointer to the first item in the linked list)
        an integer, n (the number of items to be sorted)
    output:
        a reference to a list (pointer to the sorted list)

    define variables:
        a reference to a list, A (pointer to the sorted top half of the list)
        a reference to a list, B (pointer to the sorted bottom half of the list)
        a reference to a list, temp (temporary variable used to swap)

    if r = nil then
        return nil

    if n > 1 then
        A ← sort(r, ⌊n/2⌋ )
        B ← sort(r, ⌊(n+1)/2⌋ )
        return merge( A, B )

    temp ← r
    r ← r.next
    temp.next ← nil
    return temp

一个帕斯卡实现将是：

function MergeSort(var r: list; n: integer): list;
begin
   if r = nil then 
       Result := nil
   else if n > 1 then
      Result := Merge(MergeSort(r, n div 2), MergeSort(r, (n+1) div 2) )
   else
   begin
      Result := r;
      r := r.next;
      Result.next := nil;
   end
end;

如果我的转码有效，那么这里有一个即时的C＃翻译：

list function MergeSort(ref list r, Int32 n)
{
   if (r == null)
      return null;

    if (n > 1)
    {
       list A = MergeSort(r, n / 2);
       list B = MergeSort(r, (n+1) / 2);
       return Merge(A, B);
    }
    else
    {
       list temp = r;
       r = r.next;
       temp.next = null;
       return temp;
    }
}

我现在需要的是一种对链表进行排序的并行算法。它不必是归并排序。

有些人建议复制下n个项目，其中n个项目适合单个高速缓存行，并使用这些项目生成任务。

样本数据

algorithm GenerateSampleData
    input:
        an integer, n (the number of items to generate in the linked list)
    output:
        a reference to a node (the head of the linked list of random data to be sorted)

    define variables:
        a reference to a node, head (the returned head)
        a reference to a node, item (an item in the linked list)
        an integer, i (a counter)

    head ← new node
    item ← head        

    for i ← 1 to n do
        item.value ← Random()
        item.next ← new node
        item ← item.next

    return head

因此，我们可以通过调用以下命令来生成300,000个随机项目的列表：

head := GenerateSampleData(300000);

基准测试

Time to generate 300,000 items    568 ms

MergeSort 
    count splitting variation   3,888 ms (baseline)

MergeSort
    Slow-Fast midpoint finding  3,920 ms (0.8% slower)

QuickSort
    Copy linked list to array       4 ms
    Quicksort array             5,609 ms
    Relink list                     5 ms
    Total                       5,625 ms (44% slower)

奖励阅读

• Stackoverflow：对链表进行排序的最快算法是什么？
• Stackoverflow：合并对链接列表进行排序
• 链接列表的合并排序
• 并行合并排序 O(log n)pdf，1986
• Stackoverflow：并行合并排序 （已关闭，以典型的SO书呆子时代）
• 并行合并排序 Dobbs博士，2012年3月24日
• 消除虚假分享 Dobbs博士，2009年3月14日