Monday, 22 May 2017

merge sort algorithm

package Algorithm;

public class MergeSort2 {
    //    merge sorted array a and b into c 
    static void mergeArray(int a[], int n, int b[], int m, int c[]) 
    { 
        int i, j, k; 
        i = j = k = 0; 
        while (i < n && j < m){
            c[k++]= a[i]<b[j]?a[i++]:b[j++];
        }
        while (i < n) 
            c[k++] = a[i++]; 
        while (j < m) 
            c[k++] = b[j++]; 
    } 
   
    static void sortArray(int a[],int n,int sorted[]){
        System.out.println("n="+n);
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println("++++++");
        int mid = n/2;
        if(n==1){
            sorted[0] = a[0];
            return;
        }
          if(n>1){
            int[] left = new int[mid];
            int[] right = new int[n-mid];
            int j = 0;    //    the point of a array
            for(int i=0;i<left.length;i++){
                left[i] = a[j++];
            }
            for(int i=0;i<right.length;i++){
                right[i] = a[j++];
            }
            int []leftSorted = new int[left.length];
            sortArray(left,left.length,leftSorted);
            int []rightSorted = new int[right.length];
            sortArray(right,right.length,rightSorted);
            mergeArray(left, left.length, right, right.length,sorted); 
        }
          System.out.println("after sort");
          for(int i=0;i<n;i++){
              System.out.print(sorted[i]+" ");
          }
    }
   
    public static void main(String[] args) {
        int[] a = new int[]{4,7,10,13,18,3,5,9,11,19,21};
    //    int[] a = new int[]{4};
        int[] sorted = new int[a.length];
        sortArray(a,a.length,sorted);
        for (int i = 0; i < sorted.length; ++i) {
            System.out.print(sorted[i] + " ");
        }
    }

}

Result:

n=11
4 7 10 13 18 3 5 9 11 19 21 ++++++
n=5
4 7 10 13 18 ++++++
n=2
4 7 ++++++
n=1
4 ++++++
n=1
7 ++++++
after sort
4 7 n=3
10 13 18 ++++++
n=1
10 ++++++
n=2
13 18 ++++++
n=1
13 ++++++
n=1
18 ++++++
after sort
13 18 after sort
10 13 18 after sort
4 7 10 13 18 n=6
3 5 9 11 19 21 ++++++
n=3
3 5 9 ++++++
n=1
3 ++++++
n=2
5 9 ++++++
n=1
5 ++++++
n=1
9 ++++++
after sort
5 9 after sort
3 5 9 n=3
11 19 21 ++++++
n=1
11 ++++++
n=2
19 21 ++++++
n=1
19 ++++++
n=1
21 ++++++
after sort
19 21 after sort
11 19 21 after sort
3 5 9 11 19 21 after sort
3 4 5 7 9 10 11 13 18 19 21 3 4 5 7 9 10 11 13 18 19 21 

No comments:

Post a Comment