4922. 归并排序
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 编写一个程序实现以下伪代码描述的归并排序算法。你还需报告 `Merge` 函数中比较操作的次数。 --- 归并排序伪代码 **Merge(A, left, mid, right)** 1. $ n1 = mid - left $ 2. $ n2 = right - mid $ 3. 创建数组 $ L[0...n1] $ 和 $ R[0...n2] $ 4. 对于 $ i = 0 $ 到 $ n1-1 $： - $ L[i] = A[left + i] $ 5. 对于 $ i = 0 $ 到 $ n2-1 $： - $ R[i] = A[mid + i] $ 6. 设置哨兵值：$ L[n1] = SENTINEL $，$ R[n2] = SENTINEL $ 7. 初始化指针：$ i = 0 $，$ j = 0 $ 8. 对于 $ k = left $ 到 $ right-1 $： - 如果 $ L[i] \leq R[j] $： - $ A[k] = L[i] $ - $ i = i + 1 $ - 否则： - $ A[k] = R[j] $ - $ j = j + 1 $ **Merge-Sort(A, left, right)** 1. 如果 $ left+1 < right $： - $ mid = (left + right)/2 $ - 调用 $ Merge-Sort(A, left, mid) $ - 调用 $ Merge-Sort(A, mid, right) $ - 调用 $ Merge(A, left, mid, right) $ --- ## 输入格式 第一行给出整数 $ n $。 第二行给出 $ n $ 个整数，表示序列 $ S $。 --- ## 输出格式 第一行：打印排序后的序列 $ S $。相邻元素之间用空格分隔。 第二行：打印 `Merge` 函数中的比较操作次数。 --- ## 数据范围 - $ n \leq 500,000 $ - 序列 $ S $ 中的元素满足 $ 0 \leq 元素 \leq 10^9 $ --- ## 输入 ```in1 10 8 5 9 2 6 3 7 1 10 4 ``` ## 输出 ```out1 1 2 3 4 5 6 7 8 9 10 34 ```