前端实现排序数组的合并

数组的排序与合并都是极为常见的操作。其中，排序的实现有着非常多的现成代码，这里就不再赘述了；对于无序数组的合并与排序，可以先合并，再排序。

这里要分享的则是前端实现将两个升序数组合并成一个升序数组，并支持自定义数组元素的比较函数，以及是否需要对相同元素进行去重。

export function mergeSortedArray<T = any>(
  array1: T[],
  array2: T[],
  compare?: {
    // 自定义前者是否小于后者的判断函数，默认为小于操作符
    less?: (value1: T, value2: T) => boolean,
    // 自定义去重的判断函数，默认为undefined，即不去重
    same?: (value1: T, value2: T) => boolean,  
  }
) {
  if (!array1.length) {
    return array2;
  }
  if (!array2.length) {
    return array1;
  }
  const less = compare?.less || ((value1: T, value2: T) => value1 < value2);
  if (less(array1.at(-1)!, array2[0])) {
    // 如果array1最后一个元素比array2第一个元素小，直接拼接
    return array1.concat(array2);
  }
  if (less(array2.at(-1)!, array1[0])) {
    // 如果array2最后一个元素比array1第一个元素小，直接拼接
    return array2.concat(array1);
  }
  const same = compare?.same;
  let a1 = array1;
  let a2 = array2;
  let i1 = 0, i2 = 0;
  let arrayMerged: T[] = [];
  while (true) {
    while (less(a1[i1], a2[i2])) {
      arrayMerged.push(a1[i1]);
      i1++;
      if (i1 == a1.length) {
        arrayMerged.push(...a2.slice(i2));
        return arrayMerged;
      }
    }
    // 如果定义了compare.same，将判读是否相同元素并去重
    if (same && same(a1[i1], a2[i2])) {
      i1++;
      if (i1 == a1.length) {
        arrayMerged.push(...a2.slice(i2));
        return arrayMerged;
      }
    }
    arrayMerged.push(a2[i2]);
    i2++;
    if (i2 == a2.length) {
      arrayMerged.push(...a1.slice(i1));
      return arrayMerged;
    }
    let a = a2;
    a2 = a1;
    a1 = a;
    let i = i2;
    i2 = i1;
    i1 = i;
  }
}

其实，还可以写成递归函数，代码看起来会优雅一些。对于数据量不大的数组来说，性能上带来的延迟影响也并不会很明显。