Merge Two Sorted Arrays Without Using Extra Space

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++ 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)