Merge Two Sorted Arrays Without Using Extra Space

Nov. 16, 2020 14586

We are given two sorted arrays of size m and n respectively. We need to merge both the arrays without using any other Data structure or extra space, i.e. fill the smallest m elements in the first array and the remaining n elements in the second array in a sorted manner.

Let’s understand by an example.

Input:

A[ ] = { 1, 2, 4, 6 }
B[ ] ={ 3, 5, 7 }

Output :

A[ ]= { 1, 2, 3, 4 }
B[ ]= { 5, 6, 7 }

Solution

We will use a solution similar to insertion sort, which uses the fact that both the given arrays are sorted.

Let’s say the array with the smaller first element is A and the array with the larger first element is B.

We will traverse array A and compare each element of array A to the first element of the array B.

If the first element of B is smaller than the current element of A, then we will swap both the elements and place the new element in array M to its correct position ( to make array A sorted again ).

If the first element of B is not smaller than the current element of A, then we will move to the next element of A.

Complexity analysis

Time complexity: We are traversing array A once and in the worst case we need to traverse the array B for placing the new element to its correct position.

So, the time complexity is $O(n*m)$.

Space complexity: Constant space as we are not taking any extra array.

Pseudocode for the above approach

for i = 0 to i = m
if A[i] > B[0]
swap A[i] and B[0]
j = 0
while j+1 < n and B[j] > B[j+1]
swap B[j] and B[j+1]
j++
print arrays A and B


Implementation of the above approach

• C/C++
• Python
// C++ Program for merging two
// sorted arrays without extra space

#include <bits/stdc++.h>
using namespace std;

// Function for merging two
// sorted arrays without
// extra space

void merge(int M, int N, int A[], int B[])
{
// Traverse first array and check each element

for (int i = 0; i < M; i++)
{
// check if first element of second array
// is smaller

if (A[i] > B[0])
{
swap(A[i], B[0]);
int j = 0;

// shift B[0 ] to its correct position in
// second array

while (j + 1 < N && B[j] > B[j + 1])

swap(B[j], B[j + 1]), j++;
}
}

// Print resultant array

for (int i = 0; i < M; i++)
cout << A[i] << " ";

cout << endl;

for (int i = 0; i < N; i++)
cout << B[i] << " ";
}

int main()
{

// input size of both the arrays

int M, N;
cin >> M >> N;

int A[M], B[N];

// input both the arrays

for (int i = 0; i < M; i++)
cin >> A[i];
for (int i = 0; i < N; i++)
cin >> B[i];

// function call

merge(M, N, A, B);
}

# Python Program for merging two
# sorted arrays without extra
# space

# Function for merging two
# sorted arrays without
# extra space

def merge(M, N, A, B):

# Traverse first array and check each element

for i in range(M):

# check if first element of second array
# is smaller

if A[i] > B[0]:

A[i], B[0] = B[0], A[i]

j = 0

# shift B[0 ] to its correct position in
# second array

while j + 1 < N and B[j] > B[j + 1]:

B[j], B[j + 1] = B[j + 1], B[j]
j = j + 1

# Print resultant array

print(A)
print(B)

M = 0
N = 0

# input size of both the arrays

M = int(input())

N = int(input())

# input both the arrays

A = []
B = []

for i in range(M):
temp = int(input())
A.append(temp)

for i in range(N):
temp = int(input())
B.append(temp)

# Function call

merge(M, N, A, B)


Liked the post?
Editor's Picks
0 COMMENT