30/07/2011

JAVA-Merge Sort

import java.io.*;
class merge_sort
{
public static void main(String args[])throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter the no.of elements");
int n=Integer.parseInt(br.readLine());
int i,a[]=new int[n];
for(i=0;i<n;i++)
a[i]=Integer.parseInt(br.readLine());
a=merge(a,0,a.length-1);
for(i=0;i<n;i++)
System.out.print(a[i]+"  ");
}
public static int[] merge(int a[],int p,int r)
{
int q;
if(p<r)
{
q=(p+r)/2;
merge(a,p,q);
merge(a,q+1,r);
a=mergesort(a,p,q,r);
}
return a;
}
public static int[] mergesort(int a[],int p,int q,int r)
{
int l[]=new int[q-p+2];
int R[]=new int[r-q+1];
int i,j;
for(i=0;i<l.length-1;i++)
l[i]=a[p+i];
for(j=0;j<R.length-1;j++)
R[j]=a[q+j+1];
R[j]=Integer.MAX_VALUE;
l[i]=Integer.MAX_VALUE;
i=j=0;
for(int k=p;k<=r;k++)
{
if(l[i]<=R[j])
{
a[k]=l[i];
i++;
}
else
{
a[k]=R[j];
j++;
}}
return a;
}
}

No comments:

Post a Comment