有什么方法可以优化Mergesort实现吗

Question

我为任何非常规的写作模式或任何其他明显的错误提前道歉。任何建议或提示都将不胜感激！

public class MergeSort {
    private static final int INSERTION_THRESHOLD = 8;
    public static void mergeSort(int[] x) {
        mergeSort(x, 0, x.length);
    }
    private static void mergeSort(int[] x, int start, int end) {
        int length=end-start;
        if(length<INSERTION_THRESHOLD) {
            for (int i=start; i<end; i++)
                for (int j=i; j>start && x[j-1]>x[j]; j--)
                    swap(x, j, j-1);
            return;
        }
        int mid=(start+end)>>>1;
        mergeSort(x, 0, mid);
        mergeSort(x, mid, end);
        int[] space=Arrays.copyOfRange(x, 0, mid);
        int i=0, j=mid, k=0;
        while(i<mid&&j<end)
            x[k++]=(x[j]<space[i])?x[j++]:space[i++];
        while(i<mid) 
            x[k++]=space[i++];      
    }
    private static void swap(int[] x, int n, int m) {
        int temp = x[n];
        x[n] = x[m];
        x[m] = temp;
    }

下面是一些测试案例来证明它是有效的。

    public static void main(String[] args) {
        int[] test1={ 4, 3, 2, 1, 6, 7, 4, 2 }; // 1 2 2 3 4 4 6 7
        int[] test2={ 3, 2, 3, 5, 4, 2, 1, 7 }; // 1 2 2 3 3 4 5 7
        int[] test3={ 1, 5, 4, 6, 7, 3, 2, 8 }; // 1 2 3 4 5 6 7 8
        int[] test4={ 9, 8, 7, 6, 5, 4, 3, 2 }; // 2 3 4 5 6 7 8 9
        int[] test5={-8, 7,-3, 4, 5, 1, 0,-3 }; //-8 -3 -3 0 1 4 5 7
        mergeSort(test1);
        mergeSort(test2);
        mergeSort(test3);
        mergeSort(test4);
        mergeSort(test5);
        System.out.println(Arrays.toString(test1));
        System.out.println(Arrays.toString(test2));
        System.out.println(Arrays.toString(test3));
        System.out.println(Arrays.toString(test4));
        System.out.println(Arrays.toString(test5));
    }   
}

我在这里寻找的是任何可能使其更好实现的建议或想法。我说得对吗，还是这里有一些非常搞笑的混乱？代码中是否有不必要的地方？有没有什么可以添加的东西可以让它更快/更顺利/更符合一个好的合并排序？

Answer 1

在这里，您可以了解不同语言中的不同合并排序实现，并找到最适合您的解决方案，也许可以改进现有代码。以下是该网站的PHP实现示例：

function mergesort($arr){
    if(count($arr) == 1 ) return $arr;
    $mid = count($arr) / 2;
    $left = array_slice($arr, 0, $mid);
    $right = array_slice($arr, $mid);
    $left = mergesort($left);
    $right = mergesort($right);
    return merge($left, $right);
}
function merge($left, $right){
    $res = array();
    while (count($left) > 0 && count($right) > 0){
        if($left[0] > $right[0]){
            $res[] = $right[0];
            $right = array_slice($right , 1);
        }else{
            $res[] = $left[0];
            $left = array_slice($left, 1);
        }
    }
    while (count($left) > 0){
        $res[] = $left[0];
        $left = array_slice($left, 1);
    }
    while (count($right) > 0){
        $res[] = $right[0];
        $right = array_slice($right, 1);
    }
    return $res;
}
$arr = array( 1, 5, 2, 7, 3, 9, 4, 6, 8);
$arr = mergesort($arr);
echo implode(',',$arr);

希望它能有所帮助。以下是网站：http://rosettacode.org/wiki/Sorting_algorithms/Merge_sort