咨询特定PARALLEL_MERGE_SORT并行归并排序算法的时间复杂度

首先明确：你给出的算法并非归并排序，它是典型的并行奇偶交换排序（Parallel Odd-Even Transposition Sort），属于并行排序算法的一种。

你的时间复杂度判断O(n²)是错误的，正确时间复杂度为O(n)，分析如下：

• 外层循环次数：外层循环执行Ceiling(n/2)次，属于O(n)级别的循环次数。
• 内层并行操作耗时：
  每一轮外层循环包含两轮并行操作：第一轮是所有奇数位置的PEj与PEj+1同时做比较交换，第二轮是所有偶数位置的PEj与PEj+1同时做比较交换。
  由于所有PE的比较、交换操作是并行执行的，不管n的大小，每一轮并行操作的耗时都是常数时间O(1)，无需像串行算法那样逐个处理元素。
• 总时间复杂度：外层循环O(n)次 × 每次循环内的O(1)并行操作 = O(n)。

你可能混淆了串行冒泡排序与并行奇偶交换排序的时间计算逻辑：串行冒泡排序每一轮需要O(n)时间处理元素，n轮下来是O(n²)；但在这个并行版本中，每一轮的相邻元素比较交换是同时完成的，因此时间复杂度直接降为线性。

原算法代码：

PARALLEL_MERGE_SORT
INPUT: n data elements, each on its own PEj , 1 ≤ j ≤ n.
OUTPUT: Sorted data such that PEj ≤ PEj+1 for 1 ≤ j ≤ n.
1 for i <- 1 to Ceiling(n/2)
2     for all PEj such that j is odd and 1 ≤ j <n
3         if PEj.a > PEj+1.a
4             swap(PEj.a, PE j+1.a)
5     for all PEj such that j is even and 1 ≤ j <n
6         if PEj.a > PEj+1.a
7             swap(PEj.a, PEj+1.a)

内容的提问来源于stack exchange，提问作者Muhammad Awais