81.merge-sorted-arrays.md

81. merge sorted arrays

Problem

https://bigfrontend.dev/problem/merge-sorted-arrays

Problem Description

You are given a list of sorted non-descending integer arrays, write a function to merge them into one sorted non-descending array.

merge([
  [1, 1, 1, 100, 1000, 10000],
  [1, 2, 2, 2, 200, 200, 1000],
  [1000000, 10000001],
  [2, 3, 3],
]);
// [1,1,1,1,2,2,2,2,3,3,100,200,200,1000,1000,10000,1000000,10000001]

What is time complexity of your solution?

Understanding the problem

Given a list of sorted arrays of integers, which are all in non-descending order, I am asked to write a function that is going to merge them into one array sorted in the same order.

Approach

I can solve the problem by using divide-and-conquer approach. Divide the list of sorted arrays in half, then keep dividing the two sub-lists of sorted arrays in half, until the sub-list contains only one array, cause if there is only one sorted array in the list, I can simply return that array. Then I can merge the two sorted arrays from the previous step into one and return the merged array. Keep merging the two arrays from the previous step until all arrays are merged.

To merge two sorted array I can use two pointers approach. Initially, point the first pointer to the start of the first array and the second pointer to the start of the second array, loop until both pointers point to the ends of the arrays. At each iteration, compare the elements in the two arrays the two pointers point to, if the element in the first array is smaller than the element in the second array, push the element from the first array into the empty array and move the pointer of that element to right by 1; otherwise push the element from the second array and move its pointer to right. If one of these two elements is undefined, set it to Infinity.

Solution

/**
 * @param {number[][]} arrList
 * non-descending integer array
 * @return {number[]}
 */
function merge(arrList) {
  return mergeImpl(arrList, 0, arrList.length - 1);
}

function mergeImpl(arrList, start, end) {
  if (start >= end) return arrList[end] || [];

  const mid = Math.floor((start + end) / 2);

  const left = mergeImpl(arrList, start, mid);
  const right = mergeImpl(arrList, mid + 1, end);
  return mergeSort(left, right);
}

function mergeSort(arrOne, arrTwo) {
  const mergedArr = [];
  let idxOne = 0;
  let idxTwo = 0;

  while (idxOne !== arrOne.length || idxTwo !== arrTwo.length) {
    const firstElement = arrOne[idxOne] || Infinity;
    const secondElement = arrTwo[idxTwo] || Infinity;

    if (firstElement < secondElement) {
      mergedArr.push(firstElement);
      idxOne++;
    } else {
      mergedArr.push(secondElement);
      idxTwo++;
    }
  }

  return mergedArr;
}