Parallel_sort

并行排序算法

to learn

PSRS算法

并行正则采样排序算法

复杂度分析

简单地讨论一下 PSRS 算法的复杂度。

• 在第一部分的快速排序中，时间复杂度为O(klogk)，k=n/p
• 然后，各处理器选择 p-1 个代表元素，代价为O(p)
• 再由 Proc#0 对所有送来的代表元素进行排序，然后选出主元，这里若使用快速排序，代价为O(p^2 logp^2)
• 而若使用归并排序，则所需代价为O(p^2)
• 每个处理器接收到主元后，再对有序数组进行划分，代价为O(k+p)
• 最后，各个处理器全局交换，并行归并排序，
• 每个处理器是串行的多路归并问题，时间复杂度为O(k*logp)

考虑到实际应用中，需要排序的数据长度 n 一定远远多于现有的处理器 p，此时可以视 p 为一个小常数，那么 PSRS 排序算法的时间复杂度，就可以简化为 O(klogk+k*logp)~O(klogk)

从消息复杂度的角度看，

• 播送主元的复杂度为 O(p^2+p)
• 分区合并（全局交换）部分的消息复杂度与具体算法实现相关，但其最大值不会超过 O(n)

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

上面回答部分来自ChatGPT-3.5，没有进行正确性的交叉校验。

https://dingfen.github.io/mpi&openmp/2021/01/23/psrs_sort.html