Java program for merge sort

import java.util.ArrayList;

import java.util.List;

import java.util.Scanner;

import static java.lang.System.out;

public class MergeSort {

public static void main(String args[])throws Exception

{

Scanner sc= new Scanner(System.in);

int n=sc.nextInt();

int a[]=new int[n];

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

a[i]=sc.nextInt();

new MergeSort().mergeSort(a, 0, n - 1);

for(int i=0;i<b.length;i++)

if(b[i]!=0)

out.print(b[i]+" ");

else break;

}

public void mergeSort(int[] a, int i, int j) {

if(i>=j)

return;

else

{

int mid=(i+j)/2;

mergeSort(a,i,mid);

mergeSort(a,mid+1,j);

out.println("merging start with index "+i+" "+j);

merge(a,i,j,mid);

}

}

static int b[]=new int[1000];

public void merge(int[] a, int i, int j,int mid) {

//System.out.println("yes");

int start=i,end=j;

int k=mid+1;

int l=i;

while (start<=mid&&k<=end)

{

if(a[start]<=a[k])

{

b[l++]=a[start++];

}else {

b[l++]=a[k++];

}

}

if(k>end)

for(;start<=mid;) b[l++]=a[start++];

else if(start>mid) for(;k<=end;) b[l++]=a[k++];

//copying back is very important because without this it will not merge correctly.

for(l=i;l<=j;l++)

a[l]=b[l];

}

}

OUTPUT:-

C:\Users\saty\Desktop>javac MergeSort.java

C:\Users\saty\Desktop>java MergeSort

8

34

21

56

78

9

12

5

8

merging start with index 0 1

merging start with index 2 3

merging start with index 0 3

merging start with index 4 5

merging start with index 6 7

merging start with index 4 7

merging start with index 0 7

5 8 9 12 21 34 56 78