/**

* Mergesort implementation

*

* @author William Fiset, william.alexandre.fiset@gmail.com

**/

import java.util.Arrays;

import java.util.Random;

public class Mergesort {

public static int[] mergesort( int[] ar ) {

// Base case is when a single element (which is already sorted)

int n = ar.length;

if (n == 1) return ar;

// Split array into two parts and recursively sort them

int[] left = mergesort(Arrays.copyOfRange(ar, 0, n/2));

int[] right = mergesort(Arrays.copyOfRange(ar, n/2, n));

// Combine the two arrays into one larger array

return merge(left, right);

}

// Merge two sorted arrays into a larger sorted array

private static int[] merge(int [] ar1, int[] ar2) {

int n1 = ar1.length, n2 = ar2.length;

int n = n1 + n2, i1 = 0, i2 = 0;

int[] ar = new int[n];

for(int i = 0; i < n; i++) {

if (i1 == n1) {

ar[i] = ar2[i2++];

} else if (i2 == n2) {

ar[i] = ar1[i1++];

} else {

if (ar1[i1] < ar2[i2]) {

ar[i] = ar1[i1++];

} else {

ar[i] = ar2[i2++];

}

}

}

return ar;

}

public static void main(String[] args) {

int[] array = {10, 4, 6, 4, 8, -13, 2, 3};

array = mergesort(array);

System.out.println(java.util.Arrays.toString(array));

runTests();

}

static Random RANDOM = new Random();

public static void runTests() {

final int NUM_TESTS = 1000;

for(int i = 1; i <= NUM_TESTS; i++) {

int[] array = new int[i];

for(int j = 0; j < i; j++) array[j] = randInt(-1000000, +1000000);

int[] arrayCopy = array.clone();

array = mergesort(array);

java.util.Arrays.sort(arrayCopy);

if (!java.util.Arrays.equals(array, arrayCopy))

System.out.println("ERROR");

}

}

static int randInt(int min, int max) {

return RANDOM.nextInt((max - min) + 1) + min;

}

}