### Mergesort - Sorting Algorithm - JAVA

Program:

import java.io.*;
class arraylist
{
private int[] a;
private int n;
private int[] temp;
public arraylist(int x)
{
a = new int[x];
n=0;
temp = new int[x];
}
public void insert(int e)
{
n++;
a[n]=e;
}
public void display()
{
for(int i=1;i<=n;i++)
System.out.print(a[i]+" ");
System.out.println("\n");
}
public void merge(int low,int high)
{
if(low!=high)
{
int mid=(low+high)/2;
merge(low,mid);
merge(mid+1,high);
rmerge(low,mid,high);
}
}
public void rmerge(int low,int mid,int high)
{

int i=low;int j=mid+1;int k=low;

while((i<=mid)&&(j<=high))
{
if(a[i]<=a[j])
{
temp[k]=a[i];k++;i++;
}
else
{
temp[k]=a[j];k++;j++;
}
}
while(i<=mid)
{
temp[k]=a[i];k++;i++;
}
while(j<=high)
{
temp[k]=a[j];k++;j++;
}
for(i=1;i<=high;i++)
a[i]=temp[i];
display();

}

}

class mergesort
{
public static void main(String arg[]) throws IOException
{
DataInputStream x1= new DataInputStream(System.in);

System.out.print("\nEnter the number of elements:");
arraylist ob=new arraylist(na+1);
System.out.println("Enter the elements:");
for (int k=1;k<=na;k++)
System.out.println("Before sorting:\n");
ob.display();
System.out.println("Sorting.............");
System.out.print("(MergeSort)\n\n");
ob.display();
ob.merge(1,na);
System.out.println("After sorting:\n");
ob.display();
}
}

Output:
nn@linuxmint ~ \$ javac mergesort.java
Note: mergesort.java uses or overrides a deprecated API.
Note: Recompile with -Xlint:deprecation for details.
nn@linuxmint ~ \$ java mergesort

Enter the number of elements:5
Enter the elements:
5
4
3
2
1
Before sorting:

5 4 3 2 1

Sorting.............
(MergeSort)

5 4 3 2 1

4 5 3 2 1

3 4 5 2 1

3 4 5 1 2

1 2 3 4 5

After sorting:

1 2 3 4 5

nn@linuxmint ~ \$