# Merge sort implementation with various improvements

So I was working on merge sort today, and was trying to speed it up. I would like your opinion on the implementation and if it's possible to make it faster. Besides that I was wondering if there are any mistakes that i am making code wise, things that are considered a bad practice.

I like making algorithms for fun, and then when i make them I always try to improve them. One thing that I have noticed which i couldn't wrap my head around was that when you give a reverse sorted array as input it works faster than when you don't.

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

private static void mergeDivider(int[] array, int lowBound, int highBound) {
if(lowBound < highBound) {
int middle = (lowBound + highBound)/2;

if((highBound - lowBound) <= 43){
//Found online that insertion sort is faster for n <= 43
mergeSortInsertionSortSpeedUp(array,lowBound,highBound);
} else {
//Normal divide and conquer
mergeDivider(array, lowBound, middle);
mergeDivider(array, middle + 1, highBound);

if(array[middle] > array[middle + 1]){
mergeSortMerger(array, lowBound, middle, highBound);
}
}
}
}

//Merge method
private static void mergeSortMerger(int[] array, int lowBound, int middle, int highBound) {
//Doesn't make seperate copies for left and right only makes a temporary array
int left_index = lowBound, right_index = middle + 1,temp_index = 0;
int[] temp_holder = new int[highBound - lowBound + 1];

while(left_index <= middle && right_index <= highBound){
if(array[left_index] < array[right_index]){
temp_holder[temp_index++] = array[left_index++];
} else {
temp_holder[temp_index++] = array[right_index++];
}
}

while(left_index <= middle){
temp_holder[temp_index++] = array[left_index++];
}
while(right_index <= highBound){
temp_holder[temp_index++] = array[right_index++];
}

//Put everything in the original array
for(int x = lowBound, k = 0; x <=highBound;x++,k++){
array[x] = temp_holder[k];
}
}

private static void mergeSortInsertionSortSpeedUp(int[] array, int left, int right){
for(int x = left; x <= right;x++){
int temp = array[x];
int before = x - 1;
while(before >= left && array[before] > temp){
array[before+1] = array[before];
before--;
}
array[before+1] = temp;
}
}

• was trying to speed [up merge-sort] Advice: be explicit about the base-line, think about/design a benchmark, look around if there's something useful (framework, test-set(-generator), whole benchmark). If possible, set a performance goal. For tape sort, there used to be multi-way merge-sorts: care to argue relevance thereof? – greybeard Dec 22 '18 at 17:43
• (faster with reverse sorted input is most probably due to branch prediction.) – greybeard Dec 22 '18 at 21:13

• Mandatory stability note: the sequence

    if(array[left_index] < array[right_index]){
temp_holder[temp_index++] = array[left_index++];
} else {
temp_holder[temp_index++] = array[right_index++];
}


causes loss of stability (equal elements are merged in the wrong order).

• The code still does unnecessary copying (from tmp back to array). It is unnecessary because it can be avoided. Allocate a temporary array once, then

    merge_sort subrange 0 of arr into corresponding subrange of tmp
merge_sort subrange 1 of arr into corresponding subrange of tmp
merge subranges from tmp to arr

• The insertion sort implementation is suboptimal. Testing two conditions in

    while(before >= left && array[before] > temp)


can be avoided. Take a look at the Alex Stepanov's technique (he is talking about quicksort, but the first 4 methods, which you are are only interested in, are equally applicable to your case).

• The algorithms of this kind generally look better at the semi-open ranges. Try to rewrite the code with the assumption that highBound does not belong to the range.

• Thank you for you response, I was wondering what you meant with your second point. I vaguely understand what you mean, but not completely. I get that I might be able to do it more efficiently, but everytime i have tried so far, it didn't really do anything. – SpookyBuster Dec 23 '18 at 15:06