归并排序（MergeSort） Java实现

归并排序的Java实现：

import java.util.Arrays;

public class MergeSort {

    public static void sort(Comparable[] data, int p, int r) {

        /*
         * p = 0; r = 3; total 4;
         * q = (0 + 3) / 2; q = 1;
         * sort(0, 1); sort(2,3);
         * sort(p, q); sort(q + 1, r);
         */
        if (p < r) {
            int q = (p + r) / 2;
            sort(data, p, q);
            sort(data, q + 1, r);
            merge(data, p, q, r);
        }

    }

    private static void merge(Comparable[] data, int p, int q, int r) {
        Comparable[] left = Arrays.copyOfRange(data, p, q + 1);

        Comparable[] right = Arrays.copyOfRange(data, q + 1, r + 1);

        int i = 0;
        int j = 0;
        int k = 0;
        while (k < r - p + 1) {
            if (i == left.length) {
                data[p + k] = right[j++];
            }
            else if (j == right.length) {
                data[p + k] = left[i++];
            }
            else if (left[i].compareTo(right[j]) < 0) {
                data[p + k] = left[i++];
            }
            else {
                data[p + k] = right[j++];
            }
            k++;
        }

    }

}