Merge two sorted arrays without using extra space

Given two sorted arrayA and arrayB such that arrayA has enough void spaces in it to be able to accommodate arrayB in it. Void spaces in an array are denoted using INVALID_NUM. Write a program to merge arrayB into arrayA such that resulting array is a sorted array. The expected space complexity is O(1).  

For example, if arrayA = {-3, 5, INVALID_NUM, 7, INVALID_NUM, 10, INVALID_NUM, 11, INVALID_NUM} and arrayB = {-1, 2, 6, 12}
then arrayS should be modified to array – {-3, -1, 2, 5, 6, 7, 10, 11, 12}

 

Algorithm

The algorithm to solve this problem is very similar to merge procedure of mergesort algorithm. First we move all valid elements of arrayA towards the end of it. For example, arrayA = {-3, 5, INVALID_NUM, 7, INVALID_NUM, 10, INVALID_NUM, 11, INVALID_NUM} is modified to {INVALID_NUM,INVALID_NUM,INVALID_NUM,INVALID_NUM,-3,5,7,10,11}. After this modification, k is initialized to 0, element arrayA[i] is compared with element arrayB[j] for values of ‘i’ starting from index of first valid element in arrayA up to size of arrayA and for all values of ‘j’ starting from 0 up to size of arrayB. If element arrayA[i] is less than element arrayB[j], arrayA[i] is copied to arrayA[k] otherwise arrayB[j] is copied to arrayA[k]. This compare and copy operation is done until all the elements from either arrayA or arrayB are compared and copied to arrayA. If after completion of this operation, there are still elements left in arrayB to be copied in arrayA then remaining elements from arrayB are copied towards the end of the arrayA.
The time complexity of this algorithm is O(n) with space complexity of O(1).

 

Code->

public class MergeSortedArraysInplace
{
final static int INVALID_NUM = 0;

public void inplaceMergeArrays(int[] arrayA, int[] arrayB)
{
// move all elements of arrayA with valid values towards the end
int validNumIndex = arrayA.length - 1;
for (int i = arrayA.length - 1; i >= 0; i--)
{
if (arrayA[i] != INVALID_NUM)
{
arrayA[validNumIndex] = arrayA[i];
validNumIndex -= 1;
}
}

// i: index of first valid valued element in arrayA
int i = validNumIndex + 1;
int j = 0, k = 0;

// fill-up arrayA starting from 0th index since this end of arrayA is free now
while ((i < arrayA.length) && (j < arrayB.length))
{
if (arrayA[i] < arrayB[j])
{
arrayA[k++] = arrayA[i++];
}
else
{
arrayA[k++] = arrayB[j++];
}
}

// copy any remaining elements of smaller array into larger one
while (j < arrayB.length)
{
arrayA[k++] = arrayB[j++];
}
}

public static void main(String[] args)
{
MergeSortedArraysInplace solution = new MergeSortedArraysInplace();

int[] arrayA = {-3, 5, INVALID_NUM, 7, INVALID_NUM, 10, INVALID_NUM, 11, INVALID_NUM};
int[] arrayB = {-1, 2, 6, 12};

solution.inplaceMergeArrays(arrayA, arrayB);
for (int i = 0; i < arrayA.length; i++)
{
System.out.print(arrayA[i] + ", ");
}
}
}

 

Leave a Reply

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

For Inserting code :
Paste your code in the comment form, select it and then click the language link

C | C++ | Java |

*