java - 带有 CutOFF 的 MergeSort 比常规 MergeSort 慢 - Java

Question

所以我的目标是对三种不同的算法进行计时，并在它们具有相同输入时以毫秒为单位显示执行时间的差异。我遇到的问题是，我使用截止（插入排序）的合并排序的实现比常规的慢。以下是不同的方法。我尝试调试并处理较小的输入，但我找不到问题。CUTOFF 变量的目的 - 通过更改值我应该观察到执行时间的加速。

插入排序实现：

    public static void insertionSort(int inputArray[]) {
    int j, temp;

    //start the for loop for iterating the array elements in the array
    for (int i = 1; i < inputArray.length; i++) {
        //stores the value at index at i int temp
        temp = inputArray[i];
        //assign i-1 to j
        j = i - 1;
        //while loop iterates upto j>i-1 and inputArray[j]>temp are true
        while ((j > -1) && (inputArray[j] > temp)) {
            inputArray[j + 1] = inputArray[j];

            j--;
        }
        //store temp values into particular index j+1
        inputArray[j + 1] = temp;

    }
}

对于合并排序实现，我对“CutOff”和“Regular”使用相同的合并方法。这是整个班级：

public static class MergeSort {
    private static final int CUTOFF = 0;

    void merge(int inputArray[], int lo, int mid, int hi) {
        // Creating temporary subarrays
        int leftArray[] = new int[mid - lo + 1];
        int rightArray[] = new int[hi - mid];

        // Copying our subarrays into temporaries
        for (int i = 0; i < leftArray.length; i++)
            leftArray[i] = inputArray[lo + i];
        for (int i = 0; i < rightArray.length; i++)
            rightArray[i] = inputArray[mid + i + 1];

        // Iterators containing current index of temp subarrays
        int indexLeft = 0;
        int indexRight = 0;

        // Copying from leftArray and rightArray back into array
        for (int i = lo; i < hi + 1; i++) {
            // If there are still uncopied elements in R and L, copy minimum of the two
            if (indexLeft < leftArray.length && indexRight < rightArray.length) {
                if (leftArray[indexLeft] < rightArray[indexRight]) {
                    inputArray[i] = leftArray[indexLeft];
                    indexLeft++;
                } else {
                    inputArray[i] = rightArray[indexRight];
                    indexRight++;
                }
            } else if (indexLeft < leftArray.length) {
                // If all elements have been copied from rightArray, copy rest of leftArray
                inputArray[i] = leftArray[indexLeft];
                indexLeft++;
            } else if (indexRight < rightArray.length) {
                // If all elements have been copied from leftArray, copy rest of rightArray
                inputArray[i] = rightArray[indexRight];
                indexRight++;
            }
        }
    }

    void sortNoCutOff(int inputArray[], int lo, int hi) {
        if (lo < hi) {
            //Put the cut of here
            int mid = lo + (hi - lo) / 2;
            sortNoCutOff(inputArray, lo, mid);
            sortNoCutOff(inputArray, mid + 1, hi);
            merge(inputArray, lo, mid, hi);
        }
    }

    void sortCutOff(int inputArray[], int lo, int hi) {
        if (lo <= hi + CUTOFF -1) {
            //Put the cut of here
            insertionSort(inputArray);

        } else{
            int mid = (hi + lo) / 2;
            sortCutOff(inputArray, lo, mid);
            sortCutOff(inputArray, mid + 1, hi);
            merge(inputArray, lo, mid, hi);
        }

    }
}

标签： javatime-complexitymergesortinsertion-sort