是否有任何算法使其链接列表的并行排序值得？

众所周知,Merge Sort是用于排序链表的最佳算法.

大多数合并排序都是根据数组来解释的,每一半都是递归排序的.这将使并行化变得微不足道:独立地对每一半进行排序然后合并两半.

但链表没有"中途"点; 链表一直持续到结束:

头→[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 …

Vec提供了一种排序方法(通过Deref实现),但LinkedList没有.在Rust标准库中是否存在允许对LinkedLists 进行排序的通用算法？

我需要能够按字母顺序对条目进行排序或插入.有没有一个好方法呢？

在[C/C++]中对链接列表进行排序的最佳算法是什么？