1. 算法思路
归并两个有序数组的基本思想是利用两个数组已经有序这一特性，采用双指针法逐一比较两个数组中的元素，将较小的元素依次放入新的结果数组中。这样可以确保合并后的数组仍然是有序的。
2. 理论推导
假设有两个有序数组：
-
数组 A，长度为 m
-
数组 B，长度为 n
算法的核心在于利用两个指针分别指向数组 A 和数组 B 的当前比较位置，每次比较这两个位置上的元素，将较小值加入结果数组，并移动相应指针。重复这一过程直到两个数组的元素全部合并完毕。
推导过程
-
初始条件：
-
令指针 i 指向数组 A 的起始位置（i = 0）。
-
令指针 j 指向数组 B 的起始位置（j = 0）。
-
-
比较与合并：
-
当 i < m 且 j < n 时：
-
若 A[i] ≤ B[j]，则将 A[i] 添加到结果数组中，并令 i = i + 1；
-
否则将 B[j] 添加到结果数组中，并令 j = j + 1。
-
-
-
剩余部分：
-
当其中一个数组已全部遍历完毕（例如 i = m），则将另一个数组 B 中剩下的所有元素直接追加到结果数组后面（或反之）。
-
时间复杂度推导
-
每次比较后至少移动一个指针，总共需要比较的次数不超过 m+n 次（因为每个元素最多被比较一次）。
-
整个过程需要扫描两个数组的所有元素，因此时间复杂度为：
O(m+n)
3. 算法步骤
下面给出详细的算法步骤：
-
初始化：
-
定义指针 i = 0 指向数组 A，指针 j = 0 指向数组 B。
-
定义空的结果数组 result。
-
-
循环比较：
-
当 i < m 且 j < n 时：
-
若 A[i] ≤ B[j]，则：
-
将 A[i] 添加到 result 中；
-
i = i + 1。
-
-
否则（即 A[i] > B[j]）：
-
将 B[j] 添加到 result 中；
-
j = j + 1。
-
-
-
-
处理剩余元素：
-
如果 i < m（即 A 数组还有剩余）：
-
将 A 数组中从 i 到 m-1 的所有元素依次添加到 result。
-
-
如果 j < n（即 B 数组还有剩余）：
-
将 B 数组中从 j 到 n-1 的所有元素依次添加到 result。
-
-
-
返回结果：
-
返回合并后的 result 数组。
-
算法总结
-
理论核心： 通过双指针比较两个有序数组的当前元素，并依次将较小值存入结果数组，从而保持整体有序性。
-
时间复杂度： O(m+n)，其中 m 和 n 分别为两个数组的长度。整个算法只需要扫描所有元素一次。
-
步骤清晰： 初始化指针、循环比较、处理剩余元素、返回结果。每一步都保证了算法的正确性与高效性。
