Merge Sorted Array without extra space

Given two sorted integer arrays A and B, merge B into A as one sorted array.

You may assume that A has enough space to hold additional elements from B. The number of elements initialised in A and B are m and n respectively.


For this problem, as A is assumed to have enough space, we are not allowed to create a third array.

We cannot start the merge from the beginning of the two arrays, as this will require the movement of the data.

How about starting the merge from the end of the two arrays?

Suppose aL, bL records the size of elements in A and B respectively.

We define two indexes a = aL – 1 and b = bL -1. We also define c = aL + bL – 1.

Now we compare A[a] and B[b] when b >= 0.

if A[a] >= B[b], we assign A[a] to A[c], and let a and c decrease by 1.

If A[a] < B[b] , we assign B[b] to A[c], and let b and c decrease by 1. We also need to handle the case that the elements in the beginning of B is smaller than all the elements in A.

Output: ----- Array A is --------- 1 3 4 5 6 7 8 9 10

Leave a Reply

Your email address will not be published. Required fields are marked *