2
\$\begingroup\$

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;
    }
}
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – greybeard Dec 22 '18 at 17:43
  • \$\begingroup\$ (faster with reverse sorted input is most probably due to branch prediction.) \$\endgroup\$ – greybeard Dec 22 '18 at 21:13
1
\$\begingroup\$
  • 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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – SpookyBuster Dec 23 '18 at 15:06

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.