问合并排序Java

EN

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {5, 4, 7, 2, 3, 1, 6, 2};

        print(arr);
        new MergeSort().sort(arr, 0, arr.length - 1);
    }

    private void sort(int[] arr, int lo, int hi) {
        if (lo < hi) {
            int mid = (lo + hi) / 2;
            sort(arr, lo, mid);           // recursive call to divide the sub-list
            sort(arr, mid + 1, hi);       // recursive call to divide the sub-list
            merge(arr, lo, mid, hi);      // merge the sorted sub-lists.
            print(arr);
        }
    }

    private void merge(int[] arr, int lo, int mid, int hi) {
        // allocate enough space so that the extra 'sentinel' value
        // can be added. Each of the 'left' and 'right' sub-lists are pre-sorted.
        // This function only merges them into a sorted list.
        int[] left = new int[(mid - lo) + 2];        
        int[] right = new int[hi - mid + 1];         


        // create the left and right sub-list for merging into original list.
        System.arraycopy(arr, lo, left, 0, left.length - 1);
        System.arraycopy(arr, mid + 1, right, 0, left.length - 1);

        // giving a sentinal value to marking the end of the sub-list.
        // Note: The list to be sorted is assumed to contain numbers less than 100.
        left[left.length - 1] = 100;
        right[right.length - 1] = 100;

        int i = 0;
        int j = 0;

        // loop to merge the sorted sequence from the 2 sub-lists(left and right) 
        // into the main list.
        for (; lo <= hi; lo++) {
            if (left[i] <= right[j]) {
                arr[lo] = left[i];
                i++;
            } else {
                arr[lo] = right[j];
                j++;
            }
        }
    }

    // print the array to console.
    private static void print(int[] arr) {
        System.out.println();
        for (int i : arr) {
            System.out.print(i + ", ");
        }
    }
}

private static int[] mergeSort(int[] input){
    if (input.length == 1)
        return input;

    int length = input.length/2;
    int[] left = new int[length];
    int[] right = new int[input.length - length];

    for (int i = 0; i < length; i++)
        left[i] = input[i];
    for (int i = length; i < input.length; i++)
        right[i-length] = input[i];

    return merge(mergeSort(left),mergeSort(right));
}

private static int[] merge(int[] left, int[] right){
    int[] merged = new int[left.length+right.length];
    int lengthLeft = left.length;
    int lengthRight = right.length;
    while (lengthLeft > 0 && lengthRight > 0){
        if (left[left.length - lengthLeft] < right[right.length - lengthRight]){
            merged[merged.length -lengthLeft-lengthRight] = left[left.length - lengthLeft];
            lengthLeft--;
        }else{
            merged[merged.length - lengthLeft-lengthRight] = right[right.length - lengthRight];
            lengthRight--;
        }
    }
    while (lengthLeft > 0){
        merged[merged.length - lengthLeft] = left[left.length-lengthLeft];
        lengthLeft--;
    }
    while (lengthRight > 0){
        merged[merged.length - lengthRight] = right[right.length-lengthRight];
        lengthRight--;
    }
    return merged;
}

static void mergeSort(int arr[],int p, int r) {

   if(p<r) {
        System.out.println("Pass "+k++);

        int q = (p+r)/2;
        mergeSort(arr,p,q);
        mergeSort(arr,q+1,r);
        //System.out.println(p+" "+q+" "+r);
        merge(arr,p,q,r);
    }

}

static void merge(int arr[],int p,int q,int r) {
    int temp1[],temp2[];

    //lower limit array
    temp1 = new int[q-p+1];

    //upper limit array
    temp2 = new int[r-q];

    for(int i=0 ; i< (q-p+1); i++){
        temp1[i] = arr[p+i];
    }

    for(int j=0; j< (r-q); j++){
        temp2[j] = arr[q+j+1];
    }

    int i = 0,j=0;

    for(int k=p;k<=r;k++){

        // This logic eliminates the so called sentinel card logic mentioned in Coreman
        if(i!= temp1.length
                && (j==temp2.length || temp1[i] < temp2[j])
               ) {
            arr[k] = temp1[i];
           // System.out.println(temp1[i]);
            i++;
        }
        else {
            //System.out.println(temp2[j]);
            arr[k] = temp2[j];

            j++;
        }
    }
}