个人使用了 C 语言。环境为 Linux on 12x 3.4GHz (6核12线程）。

代码编译方式：

对于并行的 mpqsort.c, mpenum.c, mpmerge.c:

1
gcc mpqsort.c -O2 -lpthread -o mpqsort

运行方式：

1
./mpqsort

对于串行的 qsort.c, enum.c, merge.c:

1
gcc qsort.c -O2 -o qsort

对于6个程序，可以在路径下用

1
make

一同生成。

并行算法伪代码

快速排序

1
2
3
4
5
6
7
8
9
10
11
para_quicksort(data, i, j, m, id)
    if (j - i) <= k or m = 0 then
        P_id call quicksort(data, i, j)
    else
        P_id: r = partition(data, i, j)
        P_id: send data[r + 1, j] to P_id + 2^(m - 1) - 1
        para_quicksort(data, i, r - 1, m - 1, id)
        para_quicksort(data, r + 1, j, m - 1, id + 2 ^ (m  - 1) - 1)
        P_id + 2^m - 1 send data[r + 1, j] back to P_id
    end if 
End

枚举排序

1
2
3
4
para_esort(i, j)
    将区间 [i, j] 划分为 nr_thrd 个区间 [Pi, Qi]
    par do esort(Pi, Qi)
End

归并排序

1
2
3
4
5
6
7
8
9
10
para_mergesort(i, j)
    if (j - i) <= len / nr_thrd then
        mergesort(i, j)
    else
        m = (i + j) / 2
        par do para_mergesort(i, m)
        par do para_mergesort(m + 1, j)
        merge
    end if
End

运行时间

串行 并行
快排 5ms 4ms
枚举 2244ms 273ms
归并 5ms 3ms

结果分析

对于快排和归并来说，由于可以并行的部分较少，耦合度较高，导致提升并不大。而对于枚举排序，则因为各线程耦合较松，共享内存可以同时读如，导致并行后优化较好。