MERGE SORT IN JAVA

MERGE SORT IN JAVA

package mergesort;

import java.util.Random;

import java.util.Scanner;

public class Demo {

public static void Display(int A[]){

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

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

}

}

public static void mergesort(int A[]){

int n=A.length;

if(n<2){

return;

}

int mid=n/2;

int LA[]=new int[mid];

int RA[]=new int[n-mid];

for(int i=0;i<mid;i++){

LA[i]=A[i];

}

for(int i=mid;i<n;i++){

RA[i-mid]=A[i];

}

mergesort(LA);

mergesort(RA);

merge(A,LA,RA);

}

public static void merge(int A[],int LA[], int RA[]){

int n=A.length;

int nl=LA.length;

int nr=RA.length;

int i=0,j=0,k=0;

while(i< nl && j<nr){

if(LA[i]<RA[j]){

A[k]=LA[i];

i++;

k++;

}else{

A[k]=RA[j];

j++;

k++;

}

}

while(i<nl){

A[k]=LA[i];

i++;

k++;

}

while(j<nr){

A[k]=RA[j];

j++;

k++;

}

}

public static void main(String args[]){

Scanner in=new Scanner(System.in);

Random random=new Random();

int s;

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

s=in.nextInt();

int A[]=new int[s];

for(int i=0;i<s;i++){

A[i]=random.nextInt(100);

}

Display(A);

mergesort(A);

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

Display(A);

}

}