1
\$\begingroup\$

I have just finished an implementation of mergesort, and I was wondering if I can further reduce the amount of reads and writes. I have looked at it for a while, and to my eyes, I cannot see anything that could really influence the amount of r/w.

public void doMergeSort(int[] array)
{
    doMergeSort(array, 0, array.length - 1);
}

public void doMergeSort(int[] array, int low, int high)
{   
    // If Low Bound Is Geater/Equal Than High Bound, Child Arrays Have Been Split As Far As They Can 
    if(low < high)
    {   
        int middle = low + (high - low) / 2;

        doMergeSort(array, low, middle);
        doMergeSort(array, middle + 1, high);

        merge(array, low, middle, high);
    }
}

private void merge(int[] parentArray, int low, int middle, int high)
{
    int pIndex = low;
    int lIndex = 0;
    int rIndex = 0;

    // Declare Arrays For The First And Second Half Of The Parent Array
    int[] leftArray = new int[(middle + 1) - low];
    int[] rightArray = new int[high - middle];

    // Populate The Left/Right Arrays
    populateArray(parentArray, leftArray, low, middle);
    populateArray(parentArray, rightArray, middle + 1, high);   

    // Loop While The Left/Right Array 'Search' Indices Are Less Than The Arrays Lengths
    while(lIndex < leftArray.length && rIndex < rightArray.length)
    {
        // Check If The Left Array Value If Smaller Than The Right Array Value (Value At Respective Index)
        reads += 2;
        if(leftArray[lIndex] < rightArray[rIndex])
        {
            reads++;
            writes++;
            parentArray[pIndex] = leftArray[lIndex];

            lIndex++;
        }
        else
        {
            reads++;
            writes++;
            parentArray[pIndex] = rightArray[rIndex];

            rIndex++;
        }

        pIndex++;
    }

    // If Looped Over All Right Array Values, Populate The Rest Of The Parent Array With Left Array Values
    while(lIndex < leftArray.length)
    {
        reads++;
        writes++;
        parentArray[pIndex] = leftArray[lIndex];

        lIndex++;
        pIndex++;
    }

    // If Looped Over All Left Array Values, Populate The Rest Of The Parent Array With Right Array Values
    while(rIndex < rightArray.length)
    {
        reads++;
        writes++;
        parentArray[pIndex] = rightArray[rIndex];

        rIndex++;
        pIndex++;
    }
}

private void populateArray(int[] originalArray, int[] newArray, int start, int end)
{
    int i = 0;

    for(int j = start; j <= end; j++)
    {
        reads ++;
        writes++;
        newArray[i] = originalArray[j];

        i++;
    }
}
\$\endgroup\$
2
\$\begingroup\$

A minor "bug"

One of the main advantages of mergesort is that it is a stable sorting algorithm. That is, it guarantees that two elements will not be swapped unnecessarily if they have the same value.

For that reason, the comparison in merge() should be implemented with:

if (leftArray[lIndex] <= rightArray[rIndex])

… so that it prefers taking from leftArray first if there is a tie.

For ints, it makes no practical difference whether the sort is stable, because two ints that are equal are indistinguishable. But it's still a good idea to use <= rather than < for the comparison, to stay true to the mergesort algorithm.

Bounds convention

In Java, a common convention is to specify a range using inclusive lower indexes and exclusive upper indexes. Examples of this convention can be seen in Arrays.copyOfRange(original, from, to) and string.substring(beginIndex, endIndex). A main advantage of this convention is that endIndex - beginIndex is the number of elements in that range, which often leads to fewer ± 1 adjustments in the code.

For example, with that convention, you would get rid of the awkward array.length - 1 in doMergeSort(), and the couple instances of (middle + 1) in merge(). Also, populateArray() would have j < end as the loop condition, which is more idiomatic. (To be fair, you would have to change the test in doMergeSort() to if (low + 1 < high).)

Copying array elements

populateArray() should be replaced by Arrays.copyOfRange() (or perhaps a wrapper around Arrays.copyOfRange() if you need the instrumentation to count reads and writes). Similarly, the loops to copy the leftover leftArray and rightArray elements could be replaced by System.arraycopy(). Both techniques would not only save a few lines of code, but might also be slightly faster than a hand-written loop.

The post-increment operator is handy for updating index counters with less verbosity:

if (leftArray[lIndex] <= rightArray[rIndex]) {
    parentArray[pIndex++] = leftArray[lIndex++];
} else {
    parentArray[pIndex++] = rightArray[rIndex++];
}

In summary, I don't see anything that can be done about the number of reads and writes, because that's just how the mergesort algorithm works. But you might be able to shorten the code a bit, and squeeze out a tiny (likely imperceptible) performance gain.

\$\endgroup\$
1
\$\begingroup\$

Do a one time allocation of a temp array and avoiding copying in the merge function by changing the direction of merge based on level of recursion for top down or pass for bottom up will speed up the merge sort. This will reduce the number of read / writes by a factor of about 2.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.