Parallel Merge

原始题目：LeetGPU - Parallel Merge

题目描述

给定两个已排序的数组 $A$（长度 $M$）和 $B$（长度 $N$），均包含按非递减顺序排列的 32 位浮点值。生成一个长度为 $M + N$ 的排序数组 $C$，包含 $A$ 和 $B$ 的所有元素，按非递减顺序排列。

实现要求

• 只允许使用 GPU 原生功能（不允许使用外部库）。
• solve 函数签名必须保持不变。
• 最终合并结果必须存储在 $C$ 中。

示例

示例 1

Input:  A = [1.0, 3.0, 5.0, 7.0], M = 4
        B = [2.0, 4.0, 6.0, 8.0], N = 4
Output: C = [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0]

示例 2

Input:  A = [-1.0, 1.0, 3.0], M = 3
        B = [2.0], N = 1
Output: C = [-1.0, 1.0, 2.0, 3.0]

约束条件

• $1 \le M, N \le 50{,}000{,}000$，$M + N \le 50{,}000{,}000$。
• $A$ 和 $B$ 均按非递减排序。
• 元素为 32 位浮点数。
• 性能测试在 $M = N = 25{,}000{,}000$ 的规模下进行。

解题思路

并行归并的关键是确定每个元素在输出中的位置。对于 $A[i]$，其在 $C$ 中的位置为 $i + rank\_in\_B(A[i])$，其中 $rank\_in\_B$ 是 $A[i]$ 在 $B$ 中的插入位置（可通过二分查找得到）。每个元素的计算是独立的，可以全并行。但二分查找对 GPU 不够友好——更好的做法是用分段并行归并（Path-based Merge），每个线程找到自己在合并路径上的位置。欢迎在 GitHub Discussions 分享你的解法。