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?
Merge Sort Implementation in Java (that seems slow...)
java;array;recursion;sorting;mergesort
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);}