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 }