Merge Sort ::  Data structure | Merge Sort using JAVA code

File Name : Mrgsrt.java

import java.util.*;

public class Mrgsrt

{

    public static void main(String[] args)

   {

      int a[],n,i;

      Scanner s=new Scanner(System.in);

      System.out.println("Enter size of the aay: ");

      n=s.nextInt(); 

      a=new int[n];

      System.out.println("Enter "+n+" Elements : ");

      for (i=0;i<n;i++)

      a[i]=s.nextInt();

      System.out.println("Elements in Array Before Merge Sort is: ");

      for (i=0;i<n; i++)

      System.out.print(a[i] + " ");

      System.out.println("\n");

      a=Merge_sort(a, n);

      System.out.println("Elements in Array After Merge Sort is: ");

      for (i=0;i<n; i++)

      System.out.print(a[i] + " ");

      System.out.println("\n");

   }

      static int[] Merge_sort(int a[], int size)

     {

        if (size>1)

       {

        int mid=size /2,first[],second[];

        first = Arrays.copyOfRange(a, 0, mid);

        first = Merge_sort(first, mid); // recursive call for first half aay

        second = Arrays.copyOfRange(a, mid, size);

        second = Merge_sort(second, size - mid); // recursive call for second half aay

        a=Merge_arrays(first, second, mid, size - mid);

     }

      return a;

  }

  static int[] Merge_arrays(int first[], int second[], int n, int m) // respectively

 {

    int a[] = new int[n + m];

    int i = 0, f = 0, s = 0;

    while(f<n && s<m)

    {

       a[i++]=(first[f]<second[s])?first[f++]:second[s++];

     }

    while(f <n)

      a[i++] = first[f++];

    while(s<m)

      a[i++]=second[s++];

    return a;

  }

}

Compilation

E:\>javac Mrgsrt.java

Execution

E:\>java Mrgsrt

Output

Enter size of the aay:

6

Enter 6 Elements :

23

5

66

1

8

99

Elements in Array Before Merge Sort is:

23 5 66 1 8 99

Elements in Array After Merge Sort is:

1 5 8 23 66 99