Merge two arrays by satisfying given constraints code example
Example: Merge two arrays by satisfying given constraints
def merge(X, Y, m, n):
# size of `X` is `k+1`
k = m + n + 1
# run if `X` or `Y` has elements left
while m >= 0 and n >= 0:
# put the next greater element in the next free position in `X[]` from the end
if X[m] > Y[n]:
X[k] = X[m]
m = m - 1
else:
X[k] = Y[n]
n = n - 1
k = k - 1
# copy the remaining elements of `Y[]` (if any) to `X[]`
while n >= 0:
X[k] = Y[n]
k = k - 1
n = n - 1
# fill `Y` with all zeroes
for i in range(len(Y)):
Y[i] = 0
# The function moves non-empty elements in `X` in the
# beginning and then merge them with `Y`
def rearrange(X, Y):
# moves non-empty elements of `X` at the beginning
k = 0
for i in range(len(X)):
if X[i]:
X[k] = X[i]
k = k + 1
# merge `X[0… k-1]` and `Y[0… n-1]` into `X[0… m-1]`
merge(X, Y, k - 1, len(Y) - 1)