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)