并行排序
归并排序
【并行排序】归并排序可以简单得扩展为并行形式，每个合并操作相互独立，因此我们以归并排序为例实现一下多线程排序。
自下而上归并排序
基本示意图如下，假设 N % 2 == 0，归并排序共 log2(N) 层，共 n-1 次合并操作
文章图片
代码如下，自底向上逐层合并，
grpSize为当前层的块大小，相邻块进行合并。repo1和repo2分别指向输入数据和临时空间，每次合并之后进行交换secondGrpSize确保了遇到数组末尾时，第二个块大小的正确性secondGrpSize == 0第二个块大小为零时，无需排序，直接拷贝输入数据到新空间即可mergeList参数为：
- 块1起始位置，
- 块2起始位置，
- 块1长度，
- 块2长度，
- 目标数组
template void mergesort(T *data, int N) {
T *temp = new T[N];
T *repo1, *repo2, *aux;
repo1 = data;
repo2 = temp;
for (int grpSize = 1;
grpSize < N;
grpSize <<= 1) {
#pragma omp parallel for
for (int stIdx = 0;
stIdx < N;
stIdx += 2 * grpSize) {
int nextIdx = stIdx + grpSize;
int secondGrpSize = min(max(0, N - nextIdx), grpSize);
if (secondGrpSize == 0) {
for (int i = 0;
i < N - stIdx;
i++)
repo2[stIdx + i] = repo1[stIdx + i];
} else
mergeList(repo1 + stIdx, repo1 + nextIdx, grpSize, secondGrpSize,
repo2 + stIdx);
}aux = repo1;
repo1 = repo2;
repo2 = aux;
}if (repo1 != data)
memcpy(data, temp, sizeof(T) * N);
delete[] temp;
}template
void mergeList(T *src1, T *src2, int len1, int len2, T *dest) {
int idx1 = 0, idx2 = 0;
int loc = 0;
while (idx1 < len1 && idx2 < len2) {
if (src1[idx1] <= src2[idx2]) {
dest[loc] = src1[idx1];
idx1++;
} else {
dest[loc] = src2[idx2];
idx2++;
}
loc++;
}for (int i = idx1;
i < len1;
i++)
dest[loc++] = src1[i];
for (int i = idx2;
i < len2;
i++)
dest[loc++] = src2[i];
} 测试：
16 线程下
$ g++ mergesort_omp_bottomup.cpp -O3 -fopenmp -g
$ ./a.out 500000000
12.9973去掉
#pragma omp parallel for 的单线程情况$ g++ mergesort_omp_bottomup.cpp -O3 -fopenmp -g
$ ./a.out 500000000
34.6137推荐阅读
- 一个选择排序算法
- 排序（归并排序）
- 【图解】9张图彻底搞懂堆排序
- vue|vue 上移 下移 删除 排序
- 必须掌握的八种基本排序算法
- 【排序】插入排序算法
- 排序之冒泡和选择
- 2019-03-02|2019-03-02 排序
- Java数据结构与算法（十）排序算法01
- 5.|5. JDK8的并行数据处理