timeit

const tsA = [[1, 'a'], [3, 'c'], [4, 'c'], [8, 'b'], [9, 'a']]
const tsB = [[1, 'c'], [2, 'b'], [3, 'c'], [4, 'a'], [5, 'b'], [7, 'a'], [9, 'a']]

function getNext(A, B) {
  let smallestA = A[0];
  let smallestB = B[0];

  if (!smallestB && smallestA) {
    return A.shift()
  }
  if (smallestB && !smallestA) {
    return B.shift()
  }
  if (smallestA < smallestB) {
    return A.shift()
  }
  return B.shift()
}

// total complexity 0(n^2)
function mergeSeries(A, B) {
  let output = [];
  let iNum;

  while (A.length !== 0 || B.length !== 0) { //#worst case: A.length + B.length O(n+n) = O(n)
    let iNum = getNext(A, B)

    // find if key exists in output already
    let currentIndex = output.findIndex(item => item[0] === iNum[0]) //#worst case: output.length O(n)

    // if so add to the existing value
    // else create a new entry
    if (currentIndex > -1) {
      output[currentIndex][1].push(iNum[1])
    } else {
      output.push([iNum[0], [iNum[1]]])
    }
  }
  return output
}


console.log(mergeSeries(tsA, tsB));