Merge two sorted arrays in Java

Merge two sorted arrays Java 

Merge two sorted arrays in java.
Lets simplify problem statement, given two sorted arrays, you need to merge it in one array such that merged array should also be sorted. 
 
Lets understand the problem statement graphically and it will be more clear,

Algorithm


Take 3 pointers,
  1. Pointer 1 pointing to 1st index of Array 1
  2. Pointer 2 pointing to 1st index of Array 2
  3. Pointer 3 pointing to 1st index of Output Array.
STEPS:
  1. Compare data of Array 1 and Array 2, whichever is smaller, copy that to Output array.
  2. Increment Pointer of Output array and Pointer of Array in which data was smaller. 
  3. If data in Array 1 and Array 2 is same, then copy data from Array 1 and Array 2 to Output array and increment pointer of all 3 Arrays.
We can follow above procedure until length of Array 1 and and Array 2 is same.
If one of the Array is smaller then repeat above procedure until length of smaller Array.
Copy the remaining element of larger array to Output array.


Merge two sorted arrays Java Program


public class Merge2SortedArrayInOne {

 public static void main(String[] args) {
  int[] mergedArr = mergeTwoSortedArray(new int[]{10,15,22,80}, new int[]{5,8,11,15,70,90});
  for (int i : mergedArr) {
   System.out.print(i + " ");
  }
 }

 public static int[] mergeTwoSortedArray(int[] arr1, int[] arr2) {
  int[] mergedArray = new int[arr1.length + arr2.length];
  int i = 0, j = 0, index = 0;

  while (i < arr1.length && j < arr2.length){
   if (arr1[i] < arr2[j])       
    mergedArray[index++] = arr1[i++];
   else        
    mergedArray[index++] = arr2[j++];               
  }

  while (i < arr1.length)  
   mergedArray[index++] = arr1[i++];

  while (j < arr2.length)    
   mergedArray[index++] = arr2[j++];

  return mergedArray;
 }
}



You may also like to see


Exception Handling Interview Question-Answer

Method Overloading - Method Hiding Interview Question-Answer

Advanced Multithreading Interview Questions-Answers In Java

Type Casting Interview Questions-Answers In Java

How Thread.join() in Java works internally

How is ambiguous overloaded method call resolved in java

 

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.

Post a Comment