Merge two sorted arrays python – Java Program to Merge Two Sorted Arrays

Merge two sorted arrays python: In the previous article, we have seen Java Program to Merge Two Arrays

In this article we are going to see how to merge two sorted arrays using java programming language.

Java Program to Merge Two Sorted Arrays

Merge two sorted arrays java: Array is a data structure which stores a fixed size sequential collection of values of single type. Where with every array elements/values memory location is associated. Each array elements have it’s own index where array index starts from 0.

In Array set of variables referenced by a single variable name and it’s array index position. It is also called as a container object which contains elements of similar type.

Declaration of an array:

dataType[] arrayName; (or)                              //Declaring an array
dataType []arrayName; (or)
dataType arr[];

Instantiation of an Array:

arrayName = new datatype[size];                    //Allocating memory to array

Combining both Statements in One:

dataType[] arrayName = new dataType[size] //Declaring and Instantiating array

Initialization of an Array:

arrayName[index-0]= arrayElement1             //Initializing the array

...

arrayName[index-s]= arrayElementS

Combining all Statements in One:

dataType arrayName[ ]={e1,e2,e3};               //declaration, instantiation and initialization

Let’s see different ways to merge two sorted arrays

Method-1: Java Program to Merge Two Sorted Arrays By Using Naive Approach

Approach:

  1. Create a new array with the combined size of arr1 and arr2.
  2. Use System.arrayCopy() method to copy those arrays into the new array.
  3. Sort the new array.

Program:

import java.util.Arrays;

public class Main
{
    public static void main(String[] args) 
    {
        int[] arr1 = { 1, 2, 3, 5, 9, 35 };
        int[] arr2 = { 4, 6, 7, 8, 10, 12, 15, 18 };
        mergeSorted(arr1, arr2);
    }

    public static void mergeSorted(int[] arr1, int[] arr2) 
    {
        int newArray[] = new int[arr1.length + arr2.length];

        // Copy first to new array from 0 to arr1.length
        System.arraycopy(arr1, 0, newArray, 0, arr1.length);

        // copy second array to new array
        System.arraycopy(arr2, 0, newArray, arr1.length, arr2.length);
        Arrays.sort(newArray);
        // display all array
        System.out.println("Array1 = " + Arrays.toString(arr1));
        System.out.println("Array2 = " + Arrays.toString(arr2));
        System.out.println("Merged Array = " + Arrays.toString(newArray));
     }
}

Output:

Array1 = [1, 2, 3, 5, 9, 35]
Array2 = [4, 6, 7, 8, 10, 12, 15, 18]
Merged Array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 15, 18, 35]

Method-2: Java Program to Merge Two Sorted Arrays By Using Gap method (Constant space)

Approach:

  1. Create scanner class object.
  2. Ask use length of the array.
  3. Initialize the array with given size.
  4. Ask the user for array elements.
  5. Start comparing elements that are far from each other rather than adjacent.
  6. If those two elements are unsorted swap them.
  7. For every pass, we calculate the gap and compare the elements towards the right of the gap. Every pass, the gap reduces to the ceiling value of dividing by 2.

Program:

import java.util.Arrays;
import java.util.Scanner;

public class Main
{
    public static void main(String[] args) 
    {
        // create scanner class object
        Scanner sc = new Scanner(System.in);
        // take input from user for array size
        System.out.print("Enter the size of arrays: ");
        int n = sc.nextInt();
        int m = sc.nextInt();
        // initialize array with size n
        int[] arr1 = new int[n];
        int[] arr2 = new int[m];

        // take input from user for array elements
        System.out.print("Enter array 1 elements: ");
        for (int i = 0; i < n; i++) 
        {
            arr1[i] = sc.nextInt();
        }
        System.out.print("Enter array 2 elements: ");
        for (int i = 0; i < m; i++) 
        {
            arr2[i] = sc.nextInt();
        }
        System.out.println("Array1 = " + Arrays.toString(arr1));
        System.out.println("Array2 = " + Arrays.toString(arr2));
        mergeSortedGap(arr1, arr2);
    }

    public static int nextGap(int gap) 
    {
        if (gap <= 1)
            return 0;
        return (gap / 2) + (gap % 2);
    }

    public static void mergeSortedGap(int[] arr1, int[] arr2) 
    {
        int i = 0, j = 0, n = arr1.length, m = arr2.length, gap = arr1.length + arr2.length;
        for (gap = nextGap(gap); gap > 0; gap = nextGap(gap)) 
        {
            // comparing elements in the first
            // array and swapping.
            for (i = 0; i + gap < n; i++)
                if (arr1[i] > arr1[i + gap]) 
                {
                    int temp = arr1[i];
                    arr1[i] = arr1[i + gap];
                    arr1[i + gap] = temp;
                }

            // comparing elements in both arrays and swapping.
            for (j = gap > n ? gap - n : 0; i < n && j < m; i++, j++)
                if (arr1[i] > arr2[j]) 
                {
                    int temp = arr1[i];
                    arr1[i] = arr2[j];
                    arr2[j] = temp;
                }

            if (j < m) 
            {
                // comparing elements in the
                // second array and swapping.
                for (j = 0; j + gap < m; j++)
                    if (arr2[j] > arr2[j + gap]) 
                    {
                        int temp = arr2[j];
                        arr2[j] = arr2[j + gap];
                        arr2[j + gap] = temp;
                    }
            }

        }
        System.out.print("Merged Array = ");
        printArray(arr1);
        printArray(arr2);

    }

    static void printArray(int[] arr) 
    {
        for (int i : arr) 
        {
            System.out.print(i + " ");
        }
    }
}

Output:

Enter the size of arrays: 5
3
Enter array 1 elements: 1 233   3 4 5 
Enter array 2 elements: 10 20 30
Array1 = [1, 2, 3, 4, 5]
Array2 = [10, 20, 30]
Merged Array = 1 2 3 4 5 10 20 30

Provided list of Simple Java Programs is specially designed for freshers and beginners to get familiarize with the concepts of Java programming language and become pro in coding.

Related Java Programs: