归并有序表或数列是计算机科学领域的一类重要的问题。归并在排序中是非常重要的一步，它在很多应用中有着举足轻重的地位。此外，归并在其它不同的应用程序中都是最基本的一部分，如寻找合适的间隔段落，优化粒子模拟，管理数据群集环境，数据库，全球情报系统，在两到三个范围和信息检索中找到最大值等。　　该研究工作的目的是弥补并行原地归并算法研究的缺乏。原地合并算法使用频繁，而关于并行原地归并算法的文献却非常有限。我们可以把这一研究缺口归因于网络在计算节点中占据支配地位，而原地归并算法此时却不适用。网络的原地归并算法就是把数据传输限制成小的信息组块，从而引起更长的处理时间和更多的通信开销。　　对比原地算法和异地算法，普通计算机如个人电脑，其扩充内存使得异地算法占据了优势地位。新并行架构的出现，凭借其有限的、不可扩展的、快速共享的内存激发了发展新一代并行原地基本算法的需要，从而节省几乎50％的内存。这类算法的应用可以使上述快速储存架构能处理更多更大的问题。　　本文，我们做出了两个主要贡献:新颖的并行k排列和完美的洗牌合并算法。第一个贡献是Saw-Teeth-Sh uffle，所提出的这个算法将完美的洗牌合并看做是一种对称分裂任务。因此，它将k排列洗牌任务看作是比赛双树洗牌任务。在有t个分区而且每个分区有k个排列时，Saw-Teeth-Shuffle的时间复杂度是O(n×log(n))，空间复杂度是O(1)。　　实验结果表明，当洗牌元素少于190时，Saw-Teeth-Shuffle算法位置变动小，因此执行时间短。这是本文工作的一个贡献。而且，它是文献中第一个运用对称分裂来代替循环领导方法来解决洗牌元素的输入。　　所提出的并行多路归并名字是Saw-Teeth-Merge。这个名字源于把多路归并看做把线性函数转化成Saw-Teeth-Merge。Saw-Teeth-Merge有一个排列洗牌的新用途。穷尽现有知识，归并排序的序列可以通过文献中少数几种方法被消减成简化元素洗牌。其算法取代了广为人知的块重排步骤创造了首次在归并排序段方面排列洗牌的用法。　　对于执行时间的分析，我们评估并证实了我们提出的Saw-Teeth-Merge算法是迄今为止文献中最快的并行多路原地归并算法。Saw-Teeth-Merge中k段就地合并的总时间复杂度是O(log(k)×n+k×log(n/k))，且能提高到O(log(k)×(n/t)+k×log(n/k))，空间复杂度是O(t×k)。　　我们证明了所提出的Saw-Teeth-Merge算法是至今为止最快的平行排列就地合并算法。它在小型数据集1上比高斯算法快307倍，比双调算法快2倍;在大型数据集2比双调算法快8.3倍，且没有大小限制。