Merge Sort Implementation in Java (that seems slow...)

Question

I decided to write my own implementation of merge sort. Here is the code:

public static int[] mergeSort(int[] array) { if (array.length <= 1) { return array; } int half = array.length / 2; return merge(mergeSort(Arrays.copyOfRange(array, 0, half)), mergeSort(Arrays.copyOfRange(array, half, array.length))); } private static int[] merge(int[] array1, int[] array2) { int len1 = array1.length, len2 = array2.length; int totalLength = len1 + len2; int[] result = new int[totalLength]; for(int i = 0, i1 = 0, i2 = 0; i < totalLength; ) { if(i1 >= len1) { while(i2 < len2) { result[i++] = array2[i2++]; } break; } else if(i2 >= len2) { while(i1 < len1) { result[i++] = array1[i1++]; } break; } if(array1[i1] > array2[i2]) { result[i++] = array2[i2++]; } else { result[i++] = array1[i1++]; } } return result; } 

When used like:

public static void main(String[] args) { Random random = new Random(); int[] array = new int[10000]; for(int i = 0, len = array.length; i < len; i++) { array[i] = random.nextInt(25000); } long before = System.nanoTime(); System.out.println(toString(array) + "\n\n" + toString(mergeSort(array)) + "\nSorted in: " + (System.nanoTime() - before) + " nanoseconds."); } private static String toString(int[] array) { StringBuffer sb = new StringBuffer("[ "); int len = array.length; for(int i = 0; i < len - 1; i++) { sb.append(array[i] + ", "); } sb.append(array[len - 1] + " ]"); return sb.toString(); } 

A sample output would be:

[ 8828, 11730, 24944, 18351, 24154, 12634, ... 18114, 3517, 221, 1808, 10474, 18710, 10050, 505, 11304, 5945, 19927, 652 ] [ 0, 14, 21, 23, 24, 25, 27, 35, 35, ... 24926, 24928, 24929, 24931, 24932, 24935, 24936, 24937, 24937, 24940, 24940, 24992 ] Sorted in 79326188 nanoseconds. 

Another sample output:

[ 11905, 14630, 17973, 9145, 10181, 20421, 24063, 13459, 5806, 22352, 1880, 24100, ... 14299, 15733, 2189, 16743, 6046, 331, 11915, 4008, 14482, 3785, 921, 13954 ] [ 3, 5, 8, 9, 9, 14, 17, 17, 18, 19, 21, 23, 26, 27, 28, 28, 30, 35, 36, 39, 44, 46, 47, 48, 50, 54, ... 24982, 24983, 24983, 24987, 24989, 24991, 24993, 24995, 24997 ] Sorted in 23808700 nanoseconds. 

The average time needed to sort each number is ((79326188 / 10000) + (23808700 / 10000)) / 2 = 515.67444 nanoseconds, which to me seems a bit slow. Is this implementation as optimized as it can get, or is there a faster way?

Answer 1

You keep allocating a new array on each split and merge, this totals up to a lot of allocations on short lived arrays.

What you can do is create a private function with more parameters so you can preallocate the merge buffer:

public void mergeSort(int[] array){ mergeSort(array, new int[array.length], 0, array.length); } private void mergeSort(int[] array, int[] buffer, int start, int end){ if(start+1< end){ mergeSort(array, buffer, start, (start+end)/2); mergeSort(array, buffer, (start+end)/2, end); merge(array, buffer, start, (start+end)/2, end); } } private void merge(int[] array, int[] buffer, int start, int mid, int end){ System.arrayCopy(array, start, buffer, start, end-start); //merge implementation int index1=start, index2=mid; int resultindex = start; while(index1<mid && index2<end){ if(buffer[index1]<buffer[index2]){ array[resultindex++] = buffer[index1++] }else{ array[resultindex++] = buffer[index2++] } } if(index1<mid) System.arrayCopy(buffer, index1, array, resultIndex, mid-index1); if(index2<end) System.arrayCopy(buffer, index2, array, resultIndex, end-index2); } 

Answer 2

General suggestion not related to the sorting implementation: You should be timing the time it takes to call and return from your mergeSort() method, not the time it takes to call System.out.println() and your toString() methods as well. Furthermore, a better microbenchmark calls for running a few iterations and then taking averages to smooth out outlying cases due to "warm-up".

Also, I will suggest using a StringBuilder instead of StringBuffer since your presumably do not require synchronization here, and append values one by one instead of concatenating them together:

stringBuilder.append(array[i]).append(", "); 

Even if you feel like timing how long it takes for your toString() method, doing both of them is likely to shave a bit of time off too if used with enough repetition.

Answer 3

Apart from review comments given by h.j.k , Your merge method can be written efficiently as given in URL which is optimized varient for merge method.After modifing the merge as mentioned in URL it reduced the overall sorting time for me.

One advice when you want to benchmark the sorting time then you should provide the constant input values . otherWise every time you will get different time as you are fetching random numbers . But as I cannot paste all the 10000, static numbers here So I have used the same strategy as used by you for getting input array .

Actual time taken to sort with the original merging strategy in consecutive runs :

12936403 13193972 13553510 13535302 13079092 13497560 

Actual time taken to sort with the modified merging strategy in consecutive runs :

9831666 10185245 10208088 10277281 10314692 10037920 

Please find below modified code:

package com.study.algorithms; import java.util.Arrays; import java.util.Random; public class MergeSort { public static void main(String[] args) { int[] array = getIntArray(); long before = System.nanoTime(); int [] sortedArray= mergeSort(array); System.out.println("Sorting took "+ (System.nanoTime() - before) +" nanoseconds "); System.out.println(toString(array) + "\n\n" + toString(sortedArray) + "\n main method completed in: " + (System.nanoTime() - before) + " nanoseconds."); } private static String toString(int[] array) { StringBuilder sb = new StringBuilder("[ "); int len = array.length; for(int i = 0; i < len - 1; i++) { sb.append(array[i] + ", "); } sb.append(array[len - 1] + " ]"); return sb.toString(); } public static int[] mergeSort(int[] array) { if (array.length <= 1) { return array; } int half = array.length / 2; return merge(mergeSort(Arrays.copyOfRange(array, 0, half)), mergeSort(Arrays.copyOfRange(array, half, array.length))); } private static int[] merge(int[] left, int[] right) { int len1 = left.length, len2 = right.length; int totalLength = len1 + len2; int[] result = new int[totalLength]; /* ORIGINAL MERGING STRATEGY */ /*for(int i = 0, i1 = 0, i2 = 0; i < totalLength; ) { if(i1 >= len1) { while(i2 < len2) { result[i++] = right[i2++]; } break; } else if(i2 >= len2) { while(i1 < len1) { result[i++] = left[i1++]; } break; } if(left[i1] > right[i2]) { result[i++] = right[i2++]; } else { result[i++] = left[i1++]; } } */ /* MODIFIED MERGING STRATEGY */ int counterForLeft =0,counterForRight=0,resultIndex=0; while(counterForLeft<len1 || counterForRight < len2){ if(counterForLeft<len1 && counterForRight < len2){ if(left[counterForLeft]<= right[counterForRight]){ result[resultIndex++] =left[counterForLeft++]; } else { result[resultIndex++] =right[counterForRight++]; } }else if(counterForLeft<len1){ result[resultIndex++] = left[counterForLeft++]; }else if (counterForRight <len2){ result[resultIndex++] =right[counterForRight++]; } } return result; } private static int[] getIntArray() { int[] array = new int[10000]; Random random = new Random(); for(int i = 0, len = array.length; i < len; i++) { array[i] = random.nextInt(25000); } return array; } }