AI solution for JavaScript Coding Question on BFE.dev
81. merge sorted arrays

One possible solution with a time complexity of O(n log n) is:

function merge(arrays) {
  let result = [];
  // Merge each pair of adjacent arrays
  while (arrays.length > 1) {
    let merged = [];
    let a = arrays.shift();
    let b = arrays.shift();
    let i = 0;
    let j = 0;
    while (i < a.length && j < b.length) {
      if (a[i] <= b[j]) {
        merged.push(a[i]);
        i++;
      } else {
        merged.push(b[j]);
        j++;
      }
    }
    while (i < a.length) {
      merged.push(a[i]);
      i++;
    }
    while (j < b.length) {
      merged.push(b[j]);
      j++;
    }
    arrays.push(merged);
  }
  // Concatenate the remaining arrays
  result = arrays[0] || [];
  for (let i = 1; i < arrays.length; i++) {
    result = result.concat(arrays[i]);
  }
  return result;
}

The solution uses a loop to repeatedly merge pairs of adjacent arrays into a single larger array until there is only one array remaining. This takes O(log n) iterations, where n is the number of input arrays.

Inside each iteration, we perform a merge of two arrays, which takes O(n) time, where n is the total number of elements in the two arrays.

Finally, we concatenate the remaining arrays, which takes O(n) time, where n is the total number of remaining elements.

Overall, the time complexity of this solution is O(n log n).