Combine Arrays

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

var a = [1, 4, 4, _, _, _]
var b = [1, 2, 3]

Without using any other arrays, 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 half 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/2 time and the remaining loops run a total of n times. n/2 + n = 3n/2 = O(n) runtime.

var a = [1, 4, 4, 0, 0, 0]
var b = [1, 2, 3]

let half = a.count / 2

for i in 0 ..< half {
  a[i + half] = a[i]
}

var i = half
var j = 0
var k = 0

while (j < half && i < a.count) {
  if a[i] < b[j] {
    a[k] = a[i]
    i += 1
  }
  else {
    a[k] = b[j]
    j += 1
  }
  
  k += 1
}

while (j < half) {
  a[k] = b[j]
  j += 1
  k += 1
}

while (i < a.count) {
  a[k] = a[i]
  i += 1
  k += 1
}

Scroll to top