Merge two sorted arrays without extra space
The problem is to merge two sorted arrays into a single sorted array without using any extra space. The given arrays are already sorted in ascending order, and the task is to merge them while maintaining the sorted order.
Example
Consider two sorted arrays:
Array X: [0, 1, 4, 4, 7, 8, 10]
Array Y: [-1, 1, 2, 3, 9, 11]
After merging the two arrays, the resulting merged array should be: [-1, 0, 1, 1, 2, 3, 4, 4, 7, 8, 9, 10, 11]
Idea to Solve the Problem
We can solve this problem using the Merge Sort approach but without using any extra space. The idea is to compare the elements of both arrays and place them in their correct position in the first array (X). Since array X has enough space to accommodate the elements from both arrays, we can perform the merging without using any additional space.
Algorithm
- Start with the first element of array X and the first element of array Y.
- Compare the two elements. a. If the element from array Y is smaller, swap it with the element from array X. b. Place the element from array Y at the correct position in array Y (by performing bubble sort on array Y). c. Continue this process for all elements in both arrays until all elements are merged.
- The merged array (array X) will now contain all elements from both arrays in sorted order.
Pseudocode
function mergeArrays(X[], Y[], sizeX, sizeY):
for i from 0 to sizeX:
if Y[0] < X[i]:
swap X[i] with Y[0]
j = 0
while Y[j] > Y[j+1]:
swap Y[j] with Y[j+1]
j = j + 1
end if
end for
end function
Code Solution
//C Program
//Merge two sorted arrays without extra space
#include<stdio.h>
//Display Array Elements
void print_array(int arr[],int size)
{
for(int i=0;i<size;i++){
printf(" %d ",arr[i] );
}
}
//Swap the value of array elements
void swap(int arr[],int i,int j)
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
//Merge two sorted arrays elements
void marge_array(int X[],int Y[],int size_x,int size_y)
{
//Display array elements
printf("\nBefore Merge ");
printf("\nFirst Array : \n");
print_array(X,size_x);
printf("\nSecond Array : \n");
print_array(Y,size_y);
int temp=0;
//merging two sorted arrays elements
for(int i=0;i<size_x;i++)
{
//Compare array Y first element into array X of i location
if(Y[0]<X[i])
{
temp=Y[0];
Y[0]=X[i];
X[i]=temp;
for(int j = 0; j < size_y-1; j++)
{
if(Y[j] > Y[j+1])
{
swap(Y,j,j+1);
}else
{
break;
}
}
}
}
printf("\n\nAfter Merge ");
printf("\nFirst Array : \n");
print_array(X,size_x);
printf("\nSecond Array : \n");
print_array(Y,size_y);
}
int main(){
int X[] = { 0, 1, 4, 4, 7, 8, 10 };
int Y[] = { -1, 1, 2, 3, 9 ,11 };
//Get The size of arrays
int size_x=(sizeof(X)/sizeof(X[0]));
int size_y=(sizeof(Y)/sizeof(Y[0]));
marge_array(X,Y,size_x,size_y);
return 0;
}
Output
Before Merge
First Array :
0 1 4 4 7 8 10
Second Array :
-1 1 2 3 9 11
After Merge
First Array :
-1 0 1 1 2 3 4
Second Array :
4 7 8 9 10 11
/*
C++ Program
Merge two sorted arrays without extra space
*/
#include<iostream>
using namespace std;
class MyArray {
public:
//Display Array Elements
void print_array(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << " " << arr[i];
}
}
//Swap the value of array elements
void swap(int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//Merge two sorted arrays elements
void marge_array(int X[], int Y[], int size_x, int size_y) {
//Display array elements
cout << "\nBefore Merge ";
cout << "\nFirst Array : \n";
this->print_array(X, size_x);
cout << "\nSecond Array : \n";
this->print_array(Y, size_y);
int temp = 0;
//merging two sorted arrays elements
for (int i = 0; i < size_x; i++) {
//Compare array Y first element into array X of i location
if (Y[0] < X[i]) {
temp = Y[0];
Y[0] = X[i];
X[i] = temp;
for (int j = 0; j < size_y - 1; j++) {
if (Y[j] > Y[j + 1]) {
this->swap(Y, j, j + 1);
} else {
break;
}
}
}
}
cout << "\n\nAfter Merge ";
cout << "\nFirst Array : \n";
this->print_array(X, size_x);
cout << "\nSecond Array : \n";
this->print_array(Y, size_y);
}
};
int main() {
MyArray obj = MyArray();
// Define collection of array elements
int X[] = {
0,
1,
4,
4,
7,
8,
10
};
int Y[] = {
-1,
1,
2,
3,
9,
11
};
//Get The size of arrays
int size_x = sizeof(X) / sizeof(X[0]);
int size_y = sizeof(Y) / sizeof(Y[0]);
obj.marge_array(X, Y, size_x, size_y);
return 0;
}
Output
Before Merge
First Array :
0 1 4 4 7 8 10
Second Array :
-1 1 2 3 9 11
After Merge
First Array :
-1 0 1 1 2 3 4
Second Array :
4 7 8 9 10 11
/*
Java Program
Merge two sorted arrays without extra space
*/
public class MyArray
{
//Display Array Elements
public void print_array(int []arr,int size)
{
for(int i=0;i<size;i++){
System.out.print(" "+arr[i] );
}
}
//Swap the value of array elements
public void swap(int []arr,int i,int j)
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
//Merge two sorted arrays elements
public void marge_array(int []X,int []Y,int size_x,int size_y)
{
//Display array elements
System.out.print("\nBefore Merge ");
System.out.print("\nFirst Array : \n");
print_array(X,size_x);
System.out.print("\nSecond Array : \n");
print_array(Y,size_y);
int temp=0;
//merging two sorted arrays elements
for(int i=0;i<size_x;i++)
{
//Compare array Y first element into array X of i location
if(Y[0]<X[i])
{
temp=Y[0];
Y[0]=X[i];
X[i]=temp;
for(int j = 0; j < size_y-1; j++)
{
if(Y[j] > Y[j+1])
{
swap(Y,j,j+1);
}else
{
break;
}
}
}
}
System.out.print("\n\nAfter Merge ");
System.out.print("\nFirst Array : \n");
print_array(X,size_x);
System.out.print("\nSecond Array : \n");
print_array(Y,size_y);
}
public static void main(String[] args) {
MyArray obj = new MyArray();
// Define collection of array elements
int X[] = { 0, 1, 4, 4, 7, 8, 10 };
int Y[] = { -1, 1, 2, 3, 9 ,11 };
//Get The size of arrays
int size_x=X.length;
int size_y=Y.length;
obj.marge_array(X,Y,size_x,size_y);
}
}
Output
Before Merge
First Array :
0 1 4 4 7 8 10
Second Array :
-1 1 2 3 9 11
After Merge
First Array :
-1 0 1 1 2 3 4
Second Array :
4 7 8 9 10 11
/*
C# Program
Merge two sorted arrays without extra space
*/
using System;
public class MyArray {
//Display Array Elements
public void print_array(int[] arr, int size) {
for (int i = 0; i < size; i++) {
Console.Write(" " + arr[i]);
}
}
//Swap the value of array elements
public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//Merge two sorted arrays elements
public void marge_array(int[] X, int[] Y, int size_x, int size_y) {
Console.Write("\nBefore Merge ");
Console.Write("\nFirst Array : \n");
print_array(X, size_x);
Console.Write("\nSecond Array : \n");
print_array(Y, size_y);
int temp = 0;
//merging two sorted arrays elements
for (int i = 0; i < size_x; i++) {
//Compare array Y first element into array X of i location
if (Y[0] < X[i]) {
temp = Y[0];
Y[0] = X[i];
X[i] = temp;
for (int j = 0; j < size_y - 1; j++) {
if (Y[j] > Y[j + 1]) {
swap(Y, j, j + 1);
} else {
break;;
}
}
}
}
Console.Write("\n\nAfter Merge ");
Console.Write("\nFirst Array : \n");
print_array(X, size_x);
Console.Write("\nSecond Array : \n");
print_array(Y, size_y);
}
public static void Main(String[] args) {
MyArray obj = new MyArray();
// Define collection of array elements
int []X = {
0,
1,
4,
4,
7,
8,
10
};
int []Y = {
-1,
1,
2,
3,
9,
11
};
//Get The size of arrays
int size_x = X.Length;
int size_y = Y.Length;
obj.marge_array(X, Y, size_x, size_y);
}
}
Output
Before Merge
First Array :
0 1 4 4 7 8 10
Second Array :
-1 1 2 3 9 11
After Merge
First Array :
-1 0 1 1 2 3 4
Second Array :
4 7 8 9 10 11
<?php
/*
Php Program
Merge two sorted arrays without extra space
*/
class MyArray {
//Display Array Elements
public function print_array($arr, $size) {
for ($i = 0; $i < $size; $i++) {
echo(" ". $arr[$i]);
}
}
//Swap the value of array elements
public function swap(&$arr, $i, $j) {
$temp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $temp;
}
//Merge two sorted arrays elements
public function marge_array(&$X, &$Y, $size_x, $size_y) {
//Display array elements
echo("\nBefore Merge ");
echo("\nFirst Array : \n");
$this->print_array($X, $size_x);
echo("\nSecond Array : \n");
$this->print_array($Y, $size_y);
$temp = 0;
//merging two sorted arrays elements
for ($i = 0; $i < $size_x; $i++) {
//Compare array Y first element into array X of i location
if ($Y[0] < $X[$i]) {
$temp = $Y[0];
$Y[0] = $X[$i];
$X[$i] = $temp;
for ($j = 0; $j < $size_y - 1; $j++) {
if ($Y[$j] > $Y[$j + 1]) {
$this->swap($Y, $j, $j + 1);
} else {
break;
}
}
}
}
echo("\n\nAfter Merge ");
echo("\nFirst Array : \n");
$this->print_array($X, $size_x);
echo("\nSecond Array : \n");
$this->print_array($Y, $size_y);
}
}
function main() {
$obj = new MyArray();
// Define collection of array elements
$X = array(0, 1, 4, 4, 7, 8, 10);
$Y = array(-1, 1, 2, 3, 9, 11);
//Get The size of arrays
$size_x = count($X);
$size_y = count($Y);
$obj->marge_array($X, $Y, $size_x, $size_y);
}
main();
Output
Before Merge
First Array :
0 1 4 4 7 8 10
Second Array :
-1 1 2 3 9 11
After Merge
First Array :
-1 0 1 1 2 3 4
Second Array :
4 7 8 9 10 11
/*
Node Js Program
Merge two sorted arrays without extra space
*/
class MyArray {
//Display Array Elements
print_array(arr, size) {
for (var i = 0; i < size; i++) {
process.stdout.write(" " + arr[i]);
}
}
//Swap the value of array elements
swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//Merge two sorted arrays elements
marge_array(X, Y, size_x, size_y) {
//Display array elements
process.stdout.write("\nBefore Merge ");
process.stdout.write("\nFirst Array : \n");
this.print_array(X, size_x);
process.stdout.write("\nSecond Array : \n");
this.print_array(Y, size_y);
var temp = 0;
//merging two sorted arrays elements
for (var i = 0; i < size_x; i++) {
//Compare array Y first element into array X of i location
if (Y[0] < X[i]) {
temp = Y[0];
Y[0] = X[i];
X[i] = temp;
for (var j = 0; j < size_y - 1; j++) {
if (Y[j] > Y[j + 1]) {
this.swap(Y, j, j + 1);
} else {
break;
}
}
}
}
process.stdout.write("\n\nAfter Merge ");
process.stdout.write("\nFirst Array : \n");
this.print_array(X, size_x);
process.stdout.write("\nSecond Array : \n");
this.print_array(Y, size_y);
}
}
function main(args) {
var obj = new MyArray();
// Define collection of array elements
var X = [0, 1, 4, 4, 7, 8, 10];
var Y = [-1, 1, 2, 3, 9, 11];
//Get The size of arrays
var size_x = X.length;
var size_y = Y.length;
obj.marge_array(X, Y, size_x, size_y);
}
main();
Output
Before Merge
First Array :
0 1 4 4 7 8 10
Second Array :
-1 1 2 3 9 11
After Merge
First Array :
-1 0 1 1 2 3 4
Second Array :
4 7 8 9 10 11
# Python 3 Program
# Merge two sorted arrays without extra space
class MyArray :
# Display Array Elements
def print_array(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1
# Swap the value of array elements
def swap(self, arr, i, j) :
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
# Merge two sorted arrays elements
def marge_array(self, X, Y, size_x, size_y) :
print("\nBefore Merge ", end = "")
print("\nFirst Array : \n", end = "")
self.print_array(X, size_x)
print("\nSecond Array : \n", end = "")
self.print_array(Y, size_y)
temp = 0
# merging two sorted arrays elements
i = 0
while (i < size_x) :
# Compare array Y first element into array X of i location
if (Y[0] < X[i]) :
temp = Y[0]
Y[0] = X[i]
X[i] = temp
j = 0
while (j < size_y - 1) :
if (Y[j] > Y[j + 1]) :
self.swap(Y, j, j + 1)
else :
break
j += 1
i += 1
print("\n\nAfter Merge ", end = "")
print("\nFirst Array : \n", end = "")
self.print_array(X, size_x)
print("\nSecond Array : \n", end = "")
self.print_array(Y, size_y)
def main() :
obj = MyArray()
X = [0, 1, 4, 4, 7, 8, 10]
Y = [-1, 1, 2, 3, 9, 11]
size_x = len(X)
size_y = len(Y)
obj.marge_array(X, Y, size_x, size_y)
if __name__ == "__main__":
main()
Output
Before Merge
First Array :
0 1 4 4 7 8 10
Second Array :
-1 1 2 3 9 11
After Merge
First Array :
-1 0 1 1 2 3 4
Second Array :
4 7 8 9 10 11
# Ruby Program
# Merge two sorted arrays without extra space
class MyArray
# Display Array Elements
def print_array(arr, size)
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
end
# Swap the value of array elements
def swap(arr, i, j)
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
end
# Merge two sorted arrays elements
def marge_array(x, y, size_x, size_y)
print("\nBefore Merge ")
print("\nFirst Array :\n")
self.print_array(x, size_x)
print("\nSecond Array :\n")
self.print_array(y, size_y)
temp = 0
# merging two sorted arrays elements
i = 0
while (i < size_x)
# Compare array Y first element into array X of i location
if (y[0] < x[i])
temp = y[0]
y[0] = x[i]
x[i] = temp
j = 0
while (j < size_y - 1)
if (y[j] > y[j + 1])
self.swap(y, j, j + 1)
else
break
end
j += 1
end
end
i += 1
end
print("\n\nAfter Merge ")
print("\nFirst Array :\n")
self.print_array(x, size_x)
print("\nSecond Array :\n")
self.print_array(y, size_y)
end
end
def main()
obj = MyArray.new()
x = [0, 1, 4, 4, 7, 8, 10]
y = [-1, 1, 2, 3, 9, 11]
size_x = x.length
size_y = y.length
obj.marge_array(x, y, size_x, size_y)
end
main()
Output
Before Merge
First Array :
0 1 4 4 7 8 10
Second Array :
-1 1 2 3 9 11
After Merge
First Array :
-1 0 1 1 2 3 4
Second Array :
4 7 8 9 10 11
/*
Scala Program
Merge two sorted arrays without extra space
*/
class MyArray {
//Display Array Elements
def print_array(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size) {
print(" " + arr(i));
i += 1;
}
}
//Swap the value of array elements
def swap(arr: Array[Int], i: Int, j: Int): Unit = {
val temp: Int = arr(i);
arr(i) = arr(j);
arr(j) = temp;
}
//Merge two sorted arrays elements
def marge_array(X: Array[Int], Y: Array[Int], size_x: Int, size_y: Int): Unit = {
print("\nBefore Merge ");
print("\nFirst Array : \n");
this.print_array(X, size_x);
print("\nSecond Array : \n");
this.print_array(Y, size_y);
var temp: Int = 0;
//merging two sorted arrays elements
var i: Int = 0;
while (i < size_x) {
//Compare array Y first element into array X of i location
if (Y(0) < X(i)) {
temp = Y(0);
Y(0) = X(i);
X(i) = temp;
var j: Int = 0;
while (j < size_y - 1 && j != -1) {
if (Y(j) > Y(j + 1)) {
this.swap(Y, j, j + 1);
} else {
j = -2;
}
j += 1;
}
}
i += 1;
}
print("\n\nAfter Merge ");
print("\nFirst Array : \n");
this.print_array(X, size_x);
print("\nSecond Array : \n");
this.print_array(Y, size_y);
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyArray = new MyArray();
var X: Array[Int] = Array(0, 1, 4, 4, 7, 8, 10);
var Y: Array[Int] = Array(-1, 1, 2, 3, 9, 11);
val size_x: Int = X.length;
val size_y: Int = Y.length;
obj.marge_array(X, Y, size_x, size_y);
}
}
Output
Before Merge
First Array :
0 1 4 4 7 8 10
Second Array :
-1 1 2 3 9 11
After Merge
First Array :
-1 0 1 1 2 3 4
Second Array :
4 7 8 9 10 11
/*
Swift Program
Merge two sorted arrays without extra space
*/
class MyArray {
//Display Array Elements
func print_array(_ arr: [Int], _ size: Int) {
var i: Int = 0;
while (i < size) {
print(" ", arr[i], terminator: "");
i += 1;
}
}
//Swap the value of array elements
func swap(_ arr: inout [Int], _ i: Int, _ j: Int) {
let temp: Int = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//Merge two sorted arrays elements
func marge_array(_ X: inout [Int], _ Y: inout [Int], _ size_x: Int, _ size_y: Int) {
print("\nBefore Merge ", terminator: "");
print("\nFirst Array : \n", terminator: "");
self.print_array(X, size_x);
print("\nSecond Array : \n", terminator: "");
self.print_array(Y, size_y);
var temp: Int = 0;
//merging two sorted arrays elements
var i: Int = 0;
while (i < size_x) {
//Compare array Y first element into array X of i location
if (Y[0] < X[i]) {
temp = Y[0];
Y[0] = X[i];
X[i] = temp;
var j: Int = 0;
while (j < size_y - 1) {
if (Y[j] > Y[j + 1]) {
self.swap(&Y, j, j + 1);
} else {
break;
}
j += 1;
}
}
i += 1;
}
print("\n\nAfter Merge ", terminator: "");
print("\nFirst Array : \n", terminator: "");
self.print_array(X, size_x);
print("\nSecond Array : \n", terminator: "");
self.print_array(Y, size_y);
}
}
func main() {
let obj: MyArray = MyArray();
var X: [Int] = [0, 1, 4, 4, 7, 8, 10];
var Y: [Int] = [-1, 1, 2, 3, 9, 11];
let size_x: Int = X.count;
let size_y: Int = Y.count;
obj.marge_array(&X, &Y, size_x, size_y);
}
main();
Output
Before Merge
First Array :
0 1 4 4 7 8 10
Second Array :
-1 1 2 3 9 11
After Merge
First Array :
-1 0 1 1 2 3 4
Second Array :
4 7 8 9 10 11
Time Complexity
- The above algorithm has a time complexity of O(m * n), where m is the size of array X and n is the size of array Y.
- In the worst case, the algorithm performs bubble sort on array Y for each element in array X.
Resultant Output Explanation
The given C program implements the algorithm to merge two sorted arrays (X and Y) into a single sorted array without using any extra space.
In the provided output, the program displays the original arrays X and Y before the merge and the arrays after the merge.
For the arrays X = [0, 1, 4, 4, 7, 8, 10] and Y = [-1, 1, 2, 3, 9, 11], after merging the arrays, the merged array X becomes [-1, 0, 1, 1, 2, 3, 4, 4, 7, 8, 9, 10, 11].
The output correctly merges the two sorted arrays without using any extra space, and the resulting array is also sorted in ascending order.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment