是否有任何算法可以使链表的并行排序值得？
大多数归并排序都是用数组来解释的，每一半都是递归排序的。这将使并行化变得微不足道：独立排序每一半，然后合并两半。
但是链表没有“中途”点；一个链表一直到它结束：
头 → [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
Pascal 实现将是：
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)
