Gfrktyl

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;

    }

}

• 
  

  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.