import java.util.*;
public class MergeSort {
    private int x[],n;
    public MergeSort(int n)
    {
        this.n=n;
        x=new int[n];
        Scanner src=new Scanner(System.in);
        for(int i=0;i<n;i++)
            x[i]=src.nextInt();
    }
    public void display()
    {
        System.out.println("The sorted elements are: ");
        for(int i=0;i<n;i++)
            System.out.print(x[i]+" ");
        System.out.println();
    }
    public void mergeSort()
    {
        int lb1,lb2,ub1,ub2=0,i,j,k,size=1;
        int temp[]=new int[n];
        while(size<n)
        {
            lb1=0;k=0;
            while(lb1+size<n)
            {
                ub1=lb1+size-1;
                lb2=ub1+1;
                ub2=lb2+size<n?lb2+size-1:n-1;
                i=lb1;
                j=lb2;
                while(i<=ub1&&j<=ub2)
                    if(x[i]<x[j])
                        temp[k++]=x[i++];
                    else temp[k++]=x[j++];
                while(i<=ub1)
                    temp[k++]=x[i++];
                while(j<=ub2)
                    temp[k++]=x[j++];
                lb1=ub2+1;
            }
            for(i=0;i<=ub2;i++)
                x[i]=temp[i];
            size=size*2;
        }
    }

}
class MergeSortExp
{
    public static void main(String args[])
    {
        Scanner src=new Scanner(System.in);
        System.out.println("Enter the no of elements");
        int n=src.nextInt();
        System.out.println();
        MergeSort obj=new MergeSort(n);
        obj.mergeSort();
        obj.display();
    }
}


O/P:

Enter the no of elements
10

12
34
67
87
4
9
55
21
100
39
The sorted elements are: 
4 9 12 21 34 39 55 67 87 100 
BUILD SUCCESSFUL (total time: 22 seconds)
