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? \$\endgroup\$