snippetjavaMinor
Merge sort could work 10 times faster
Viewed 0 times
mergecouldfastertimesworksort
Problem
I am implementing merge sort in Java and I have a performance problem in this method:
If I replace this method content with the content of the comment, like this:
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?
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:
Totally untested, I would try something like this:
-
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.