Merge Sort > Java Program

Analysis of Algorithm

Merge Sort > Java Program

import java.io.*;  
class MergeSort  
{  
public static void main(String args[ ])  
{  

int i,n=0;  
int increments[]={5,3,1};   
int x[]=new int[25];  
DataInputStream in = new DataInputStream(System.in);  
try  
{  
System.out.print("Enter how many numbers to be sorted : ");  
n = Integer.parseInt(in.readLine());  
System.out.println("Enter numbers ");  
for(i=0;i<n;i++)  
{  
x[i] = Integer.parseInt(in.readLine());  
}  
}  
catch(Exception e)  
{  
System.out.println("I/O Error");    
}  
merge(x,n);  
System.out.println("\nSorted Elements are :");  
for(i=0;i<n;i++)  
System.out.print("\t"+x[i]);   
}  
static void merge(int x[],int n)  
{  
int sub[] = new int[25];  
int i,j,k,l1,l2,u1,u2,size;  
int p=1;  
size=1;  
while(size<n)  
{  
l1=0;  
k=0;  
while((l1+size)<n)  
{  
l2=l1+size;  
u1=l2-1;  
u2=((l2+size-1)<n)?(l2+size-1):(n-1);  
for(i=l1,j=l2;i<=u1 && j<=u2;k++)  
if(x[i]<=x[j])  
sub[k]=x[i++];  
else  sub[k]=x[j++];  
for(;i<=u1;k++)  
sub[k]=x[i++];  
for(;j<=u2;k++)  
sub[k]=x[j++];  
l1=u2+1;  
}  
for(i=l1;k<n;i++)  
sub[k++]=x[i];  
for(i=0;i<n;i++)  
x[i]=sub[i];  
size*=2;  
System.out.print("AFTER PASS:"+(p++));  
for(int z=0;z<n;z++)  
{  
System.out.print("\t"+x[z]);  
} 
System.out.println();  
}  
}  
}  
/*OUTPUT:  
Enter how many numbers to be sorted : 
8  
Enter numbers in any order....  
95  75  46  35  15  46  84  55  
AFTER PASS:1     75      95      35      46      15      46      55      84  
AFTER PASS:2     35      46      75      95      15      46      55      84  
AFTER PASS:3     15      35      46      46      55      75      84      95     
Sorted Elements are :          
15      35      46      46      55      75      84      95   */