时间复杂度为 O(m + n) ，可简称为 O(n)

排序流程

1. 在两个数组中，从第一项开始，各自设一个指针
2. 将两指针对应的元素进行比较，将较小的放入最终数组中，若两元素相同，就都放入最终数组中，若有一个指针没有数据，则将有数据的指针放入最终数组中
3. 比较完成后，移除元素的数组的指针右移，直至两个指针都不再有元素。

代码实现

function twoPointerSort(arr1, arr2) {const result = [];let i = 0;let j = 0;// 只要 arr1 或 arr2 还有值，就继续循环while (arr1[i] != null || arr2[j] != null) {const v1 = arr1[i];const v2 = arr2[j];// arr1 和 arr2 都没有值了，则停止if (v1 == null && v2 == null) {break;}if (v1 < v2 || v2 == null) {// v1 较小，则只拼接 v1result.push(v1);i++;}if (v1 > v2 || v1 == null) {// v2 较小，则只拼接 v2result.push(v2);j++;}if (v1 === v2) {// v1 v2 相等，则都拼接result.push(v1);i++;result.push(v2);j++;}}return result;
}

测试效果

const arr1 = [1, 3, 5, 7, 9];
const arr2 = [2, 4, 6, 8];const finalArray = twoPointerSort(arr1, arr2);console.log(finalArray);

结果

[ 1, 2, 3, 4, 5, 6, 7, 8, 9]

为什么不用 concat + sort 实现 ？

因为时间复杂度高，至少是 O(n*logn)

const res = arr1.concat(arr2).sort((a, b) => a - b)
console.log(res)