Mergesort.java

import java.util.Arrays;
import java.util.Random;

public class Mergesort {

    public static int[] mergeSort(int[] arr) {
        if (arr.length <= 1) {
            return arr;
        }

        int[] left, right;

        left = Arrays.copyOfRange(arr, 0, arr.length / 2);
        right = Arrays.copyOfRange(arr, arr.length / 2, arr.length);

        left = mergeSort(left);
        right = mergeSort(right);

        return merge(left, right, arr);

    }

    private static int[] merge(int[] left, int[] right, int result[]) {
        int i = 0, j = 0, z = 0;
        
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[z++] = left[i++];
            } else {
                result[z++] = right[j++];
            }
        }

        while (i < left.length) {
            result[z++] = left[i++];
        }

        while (j < right.length) {
            result[z++] = right[j++];
        }
        
        return result;
    }
    
    public static void coderoddeMergesort(final int[] array) {
        coderoddeMergesort(array, 0, array.length);
    }
    
    public static void coderoddeMergesort(final int[] array,
                                          final int fromIndex,
                                          final int toIndex) {
        
        if (fromIndex > toIndex) {
            throw new IllegalArgumentException(
                    "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
        }
        
        final int rangeLength = toIndex - fromIndex;
        
        if (rangeLength < 2) {
            // Trivially sorted.
            return;
        }
        
        // Allocate the auxiliary buffer only ONCE.
        final int[] aux = Arrays.copyOfRange(array, fromIndex, toIndex);
        // Do actual sorting.
        coderoddeMergesortImpl(aux, 
                               array, 
                               0, 
                               rangeLength,
                               fromIndex,
                               toIndex);
    }
    
    private static void coderoddeMergesortImpl(final int[] source,
                                               final int[] target,
                                               final int sourceFromIndex,
                                               final int sourceToIndex,
                                               final int targetFromIndex,
                                               final int targetToIndex) {
        final int rangeLength = sourceToIndex - sourceFromIndex;
        
        if (rangeLength < 2) {
            return;
        }
        
        final int sourceMiddleIndex = sourceFromIndex + (rangeLength >>> 1);
        final int targetMiddleIndex = targetFromIndex + (rangeLength >>> 1);
        
        coderoddeMergesortImpl(target,
                               source,
                               targetFromIndex,
                               targetMiddleIndex,
                               sourceFromIndex,
                               sourceMiddleIndex);
        
        coderoddeMergesortImpl(target,
                               source,
                               targetMiddleIndex,
                               targetToIndex,
                               sourceMiddleIndex,
                               sourceToIndex);
        
        coderoddeMerge(source,
                       target,
                       targetFromIndex,
                       sourceFromIndex,
                       sourceMiddleIndex,
                       sourceToIndex);
    }
    
    private static void coderoddeMerge(final int[] source, 
                                       final int[] target,
                                       int targetOffset,
                                       int left,
                                       int right,
                                       final int rightBound) {
        final int leftBound = right;
        
        while (left < leftBound && right < rightBound) {
            target[targetOffset++] =
                    source[left] < source[right] ? 
                    source[left++] :
                    source[right++];
        }
        
        System.arraycopy(source, left, target, targetOffset, leftBound - left);
        System.arraycopy(source, 
                         right, 
                         target, 
                         targetOffset, 
                         rightBound - right);
    }

    public static void main(final String[] args) {
        final long seed = System.nanoTime();
        final Random random = new Random(seed);
        System.out.println("Seed = " + seed);
        
        test(random);
        warmup(random);
        
        final int[] array1 = random.ints(5_000_000L).toArray();
        int[] array2 = array1.clone();
        
        long startTime = System.nanoTime();
        coderoddeMergesort(array1);
        long endTime = System.nanoTime();
        
        System.out.printf("coderoddeMergesort() in %.0f milliseconds.\n",
                          (endTime - startTime) / 1e6);
        
        startTime = System.nanoTime();
        array2 = mergeSort(array2);
        endTime = System.nanoTime();
        
        System.out.printf("mergeSort() in %.0f milliseconds.\n",
                          (endTime - startTime) / 1e6);
        
        System.out.println("Arrays are same: " + Arrays.equals(array1, array2));
    }
    
    private static void test(final Random random) {
        for (int i = 0; i < 1000; ++i) {
            final int[] array1 = random.ints(1000L).toArray();
            final int[] array2 = array1.clone();
            final int fromIndex = random.nextInt(100);
            final int toIndex = array1.length - random.nextInt(100);
            
            coderoddeMergesort(array1, fromIndex, toIndex);
            Arrays.sort(array2, fromIndex, toIndex);
            
            if (!Arrays.equals(array1, array2)) {
                throw new RuntimeException(
                        "Arrays.sort and coderoddeMergesort dis not agree.");
            }
        }
    }
    
    private static void warmup(Random random) {
        for (int i = 0; i < 100; ++i) {
            final int[] array1 = random.ints(50000L).toArray();
            int[] array2 = array1.clone();
            
            coderoddeMergesort(array1);
            array2 = mergeSort(array2);
            
            if (!Arrays.equals(array1, array2)) {
                throw new RuntimeException(
                        "Arrays.sort and coderoddeMergesort dis not agree.");
            }
        }
    }
}