HiveBrain v1.2.0
Get Started
← Back to all entries
snippetjavaMinor

Merge sort could work 10 times faster

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
mergecouldfastertimesworksort

Problem

I am implementing merge sort in Java and I have a performance problem in this method:

private static void marge(int[] source, int[] buffer, int startingIndex, int count) {
        int index1 = startingIndex;
        int index2 = startingIndex + count / 2;
        int maxIndex1 = index2;
        int maxIndex2 = startingIndex + count;

        for(int i = 0; i = maxIndex2 || (index1 < maxIndex1 && source[index1] < source[index2])){
                buffer[startingIndex + i] = source[index1];
                index1++;
            }
            else{
                buffer[startingIndex + i] = source[index2];
                index2++;
            }
        }

//      System.arraycopy(source, startingIndex, buffer, startingIndex, count);
    }


If I replace this method content with the content of the comment, like this:

private static void marge(int[] source, int[] buffer, int startingIndex, int count) {
    System.arraycopy(source, startingIndex, buffer, startingIndex, count);
}


It performs 10 to 20 times faster. I understand that I have more calculations in my original method but "10 to 20 times" seems too much for me.

Do you have any idea how to improve performance?

Solution

Some pointers:

-
You keep adding 2 numbers here: startingIndex + i, that could probably be avoided if you went for(int i = startIndex; i

-
Since
++ happens post evaluation you could simply do buffer[startingIndex + i] = source[index1++];, it does not have to be a separate statement

-
Short circuit logic : if
index2 >= maxIndex2, then you should probably have a System.arraycopy copy that fills the rest into index1 and get out. You could the same for when index1 > maxIndex1 but obviously you would fill into index2 then

From a naming perspective, I would rather read
upperIndex and lowerIndex than index1 and index2`

Totally untested, I would try something like this:

private static void merge(int[] source, int[] buffer, int startingIndex, int count) {
    int lowerIndex = startingIndex;
    int lowerBound = startingIndex + count / 2;
    int upperIndex = lowerBound;
    int upperBound = startingIndex + count;

    for(int i = startingIndex ; i = upperBound ){
          System.arraycopy(source, lowerIndex , buffer, i, i - startingIndex );
          return;
        }
        if(lowerIndex >= lowerBound ){
          System.arraycopy(source, upperIndex , buffer, i, i - startingIndex );
          return;
        }
        buffer[i] = source[lowerIndex] < source[upperIndex] ? source[lowerIndex++] : source[upperIndex++]
    }
}

Code Snippets

private static void merge(int[] source, int[] buffer, int startingIndex, int count) {
    int lowerIndex = startingIndex;
    int lowerBound = startingIndex + count / 2;
    int upperIndex = lowerBound;
    int upperBound = startingIndex + count;

    for(int i = startingIndex ; i < upperBound ; i++){
        if(upperIndex >= upperBound ){
          System.arraycopy(source, lowerIndex , buffer, i, i - startingIndex );
          return;
        }
        if(lowerIndex >= lowerBound ){
          System.arraycopy(source, upperIndex , buffer, i, i - startingIndex );
          return;
        }
        buffer[i] = source[lowerIndex] < source[upperIndex] ? source[lowerIndex++] : source[upperIndex++]
    }
}

Context

StackExchange Code Review Q#46198, answer score: 6

Revisions (0)

No revisions yet.