Friday, April 15, 2011

Merge Sort


import java.util.Scanner;
class MergeSort
{
                static void Merge(int x[],int n)
    {
        int sub[] = new int[25];
        int i,j,k,l1,l2,u1,u2,size;
        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;
        }
    }
   
    public static void main(String args[ ])
                {
                                int i,n=10;
        Scanner in = new Scanner(System.in);
        System.out.print("Enter how many numbers to be sorted : ");
        n = in.nextInt();
        int x[]=new int[n];
        System.out.println("Enter numbers");
        for(i=0;i<n;i++)
            x[i] = in.nextInt();
        Merge(x,n);
        System.out.println("\nSorted Elements are :");
        for(i=0;i<n;i++)
        System.out.print(x[i] + "  ");
    }
}