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

1. Start with the first element of array X and the first element of array Y.
2. 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.
3. 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
• C++
• Java
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

//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;
}

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;
}

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

 
  }
}

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);
	}
}

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();

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();

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

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

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);
	}
}

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();

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.