Combine Arrays

You are given two arrays, A and B, both contain elements in ascending order. Array A has allocated enough space to fit all elements from both A and B in it.

const a = [1,4,4,6,_,_,_,_,_]
const b = [1,2,3,5,9] 

Combine all numbers of A and B into A in ascending order.

One way to solve this is to copy elements of B into the extra space allocated in A and then sort A. The runtime for this is O(n log n).

A faster solution is to shift all elements in A to the right side of A and then insert items into A starting from front. This step is similar to the merge function of merge sort.

For n elements, the first loop runs in < n time and the second loop runs in n time. n + n = 2n = O(n) runtime.

const a = [1,4,4,6,0,0,0,0,0]
const b = [1,2,3,5,9]

let h = 0
for (let i = b.length; i < a.length; i++) {
  a[i] = a[h]
  h++
}

let j = b.length
let k = 0

for (let i = 0; i < a.length; i++) {
  if (a[j] <= b[k]) {
    a[i] = a[j]
    j++
  } else {
    a[i] = b[k]
    k++
  }
}

console.log(a)