归并排序

 

归并排序是一种相当稳健的排序算法，无论何种输入序列，其期望时间复杂度和最坏时间复杂度都是O(nlogn), 这已经达到了基于比较排序算法的渐进下界。因此归并排序时常会用于对可能导致quicksort退化的序列排序。

归并排序是典型的分治算法，常见的实现如下：

   private void merge(int[] arr, int lowerPtr, int upperPtr, int upperBound) {

        if (result.length < arr.length) {
            throw new RuntimeException("arr length too short.");
        }

        int j = 0;
        int lowerBound = lowerPtr;
        int mid = upperPtr - 1;
        int n = upperBound - lowerBound + 1;

        while (lowerPtr <= mid && upperPtr <= upperBound) {
            if (result[lowerPtr] < result[upperPtr]) {
                arr[j++] = result[lowerPtr++];
            } else {
                arr[j++] = result[upperPtr++];
            }
        }

        while (lowerPtr <= mid) {
            arr[j++] = result[lowerPtr++];
        }

        while(upperPtr <= upperBound) {
            arr[j++] = result[upperPtr++];
        }

        for (int i = 0; i < n; i++) {
            result[lowerBound + i] = arr[i];
        }
    }

    public void recMergeSort(int[] arr, int lower, int upper) {
        if (lower == upper) {
            return;
        } else {
            int mid = (lower + upper) >> 1;
            recMergeSort(arr, lower, mid);
            recMergeSort(arr, mid + 1, upper);
            merge(arr, lower, mid + 1, upper);
        }
    }