Merge Sort Implementation in Java (that seems slow...) I decided to write my own implementation of merge sort. Here is the code:

public static int[] mergeSort(int[] array) {
    if (array.length &lt;= 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 &lt; totalLength; ) {
        if(i1 &gt;= len1) {
            while(i2 &lt; len2) {
                result[i++] = array2[i2++];
            }
            break;
        } else if(i2 &gt;= len2) {
            while(i1 &lt; len1) {
                result[i++] = array1[i1++];
            }
            break;
        }
        if(array1[i1] &gt; 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 &lt; 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 &lt; 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?
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.