0

Recently I was testing two variations of the merge method in Mergesort and one turns our to be slightly faster than the other. For a large enough input (say, an array of 10-100 million or more randomly ordered elements), one merge method takes around 100ms longer than the other.

Here's the one taking more time:

private static void merge(int[] a, int low, int mid, int hi) {
    int temp[] = new int[(hi - low) + 1];

    int cLeft = low;
    int cRight = mid + 1;
    int cTemp = 0;

    while (cLeft <= mid && cRight <= hi) {
        if (a[cLeft] <= a[cRight]) {
            temp[cTemp++] = a[cLeft++];
        } else {
            temp[cTemp++] = a[cRight++];
        }
    }

    //copy the remaining left elements to the right end
    System.arraycopy(a, cLeft, a, low + cTemp, mid - cLeft + 1);

    //copy temp to a
    System.arraycopy(temp, 0, a, low, cTemp);
}

...and this is the faster one

private static void merge(int[] list, int lowIndex, int midIndex, int highIndex) {
    int[] L = new int[midIndex - lowIndex + 2];

    for (int i = lowIndex; i <= midIndex; i++) {
        L[i - lowIndex] = list[i];
    }
    L[midIndex - lowIndex + 1] = Integer.MAX_VALUE;
    int[] R = new int[highIndex - midIndex + 1];

    for (int i = midIndex + 1; i <= highIndex; i++) {
        R[i - midIndex - 1] = list[i];
    }
    R[highIndex - midIndex] = Integer.MAX_VALUE;
    int i = 0, j = 0;

    for (int k = lowIndex; k <= highIndex; k++) {
        if (L[i] <= R[j]) {
            list[k] = L[i];
            i++;
        } else {
            list[k] = R[j];
            j++;
        }
    }
}

Both variations of MergeSort are given different arrays of same length with same elements at identical positions as their input. In other words, input of one algorithm is a copy of input of the other.

Although the difference in running time is negligible (the average running time doesn't change, i.e. remains 100ms, no matter how much we increase the size after 1 million mark.), I am eager to know what makes the faster merge faster. For me, the former method is cleaner and easier to implement. However, if the other one remains faster, I probably will switch to that.

  • Anyone...any idea? –  Mar 07 '18 at 06:50
  • 1
    Maybe because the first one allocates an array of size ~n while the second makes two of size ~n/2, which is easier to do? – saagarjha Mar 07 '18 at 07:17
  • 1
    The faster one doesn't have copy remainder of left elements, and both should have copy remainder of left and right elements. If the goal is better performance, it would be better to do a one time allocation of the temp array (by a helper / entry function) and use indexing to separate the original and working array into runs during the merge sort. – rcgldr Mar 07 '18 at 09:52
  • 2
    100 ms in Java? That's a joke. Java starts slow, any measurement needs a few seconds at least, unless you want to measure the transient behavior, which is completely irrelevant for long running programs. [Correct benchmarking](https://stackoverflow.com/a/513259/581205). `+++` There are tons of factors and without starting a new JVM for each measurement, you [needn't bother measuring](https://codereview.stackexchange.com/questions/52315/efficiently-checking-if-a-number-is-divisible-by-3/52331#comment91771_52344). – maaartinus Mar 07 '18 at 18:30

0 Answers0