Merge Sort [Java Implementation]

                                        Merge Sort

                              [Java Implementation]

Merge Sort uses the technique of  Divide and Conquer technique to sort the elements.It is the best sorting algorithm and thus its efficiency is O(nlogn).It divides the elements into sub-small arrays and the use merging algorithm to merge the two sub-arrays in a sorted manner.It is easy algorithm to design as we have to put some effort for only merging algorithm.

For more details:- https://en.wikipedia.org/wiki/Merge_sort

Image shows the working of merge sort:-

As shown in figure merging of two arrays will happen as the small element(as present index)  from two sub arrays is put in third array and further same algorithms works and finally we get the full sorted array as a result.

Efficiency   :-       O(nlogn)

Program:-

/**

 * @(#)MyMergeSort.java

 *

 *

 * @author Suyash Bhalla

 * @version 1.00 2015/8/16

 */

class MyMergeSort {

    public static void sort(int ar[],int low,int high){

   

    if(low<high){

    int mid=(low+high)/2;

    sort(ar,low,mid);

    sort(ar,mid+1,high);

    merge(ar,low,mid,high);

    }

   

    }

    

    

    public static void merge(int ar[],int l,int m,int r){

   

    int i=0,j=0,k;

    int n1=m-l+1,n2=r-m;

   

    int L[]=new int[n1],R[]=new int[n2];

    for(i=0;i<n1;i++){ L[i]=ar[l+i]; } for(j=0;j<n2;j++){ R[j]=ar[m+j+1]; }

    i=0;j=0;k=l;

    while(i<n1&&j<n2){

   

    if(L[i]<=R[j]){

    ar[k++]=L[i++];

    }else{

    ar[k++]=R[j++];

    }

   

    }

   

    while(i<n1){

    ar[k++]=L[i++];

    }

   

    while(j<n2){

    ar[k++]=R[j++];

    }

    }

    

    

    public static void main(String args[]){

    

   

    int ar[]={90,1,89,77,15,10,20,28,91,1,3,9,6,12,99,88,78,26};

   

    sort(ar,0,ar.length-1);

    

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

    System.out.println(ar[i]);

    }

    

    }

}

Output:-

1

1

3

6

9

10

12

15

20

26

28

77

78

88

89

90

91

99

------------------X--------------X------------------X------------------X-------------X----------------