0️⃣归并排序流程

1. 分割过程：将待排序数组等分为左右子数组，再对左右子数组递归式等分，直至不可分割
2. 合并过程：将所有子数组两两递归合并，逐步得到较大有序数组，直到得到完整有序数组

1️⃣传统的并行归并

1. 线程映射：为每个合并操作分配一个线程

   

2. 问题所在：随着归并的进行$\to \{\begin{array}{l}同时合并的数组减少\to 并行工作的线程减少\\ \\ 单次合并的数组更长\to 单线程运行时间变长\end{array}\to$导致大量线程排序完成前空闲

2️⃣并行合并历程

1. 线程映射：为合并操作中每个列表的每个元素都分配一个线程

   

2. 并行合并历程：对于给定量已排序的待合并表$A$与$B$

   
   • 线程索引： 为两列表中每个元素(邻居)分配一线程，线程索引$=$元素在自己列表里的位置索引
   • 位置计算：通过二分查找，找出两列表中每个元素插入对方列表后的索引
   • 列表合并：将每个元素的两个索引相加即得元素在新的合并列表中的索引，由此得到合并列表