Merge Sort Program

Merge Sort Program:


import java.util.Scanner;
class Merge_Sort
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        int ar[]={16,8,6,12,14,9,4,5,3,10};
        //int ar[]={10,8,12,16,9,7,5,15,14,3};
        //int ar[]={10,16,8,12,15,6,3,9,5,7};
        //int ar[]={16,15,14,12};
        ar=mergeSort(ar);
        for(int x=0;x<=ar.length-1;x++)
        {
            System.out.print(ar[x] + "  ");
        }
    }

    public static void merge(int ar[],int left[],int right[])
    {
        int nL=left.length;
        int nR=right.length;
        int i=0,j=0,k=0;
        while(i<nL && j<nR)
        {
            if(left[i]<right[j])
            {
                ar[k]=left[i];
                i++;
            }
            else
            {
                ar[k]=right[j];
                j++;
            }
            k++;
        }
        while(i<nL)
        {
            ar[k]=left[i];
            i++;
            k++;
        }
        while(j<nR)
        {
            ar[k]=right[j];
            j++;
            k++;
        }
    }

    public static int[] mergeSort(int ar[])
    {
        if(ar.length<2)
        {
            return ar;
        }
        int mid = ar.length/2;
        int left[]=new int[mid];
        int right[]=new int[ar.length-mid];
        for(int x=0;x<=mid-1;x++)
        {
            left[x]=ar[x];
        }
        for(int x=mid;x<=ar.length-1;x++)
        {
            right[x-mid]=ar[x];
        }
        int l[]=mergeSort(left);
        int r[]=mergeSort(right);
        merge(ar,l,r);
        return ar;
    }
}

Post a Comment

0 Comments