import java.util.Random;

class MergeSort {

public static void main (String[] args) {

/*

final int LENGTH = 100;

Random rand = new Random();

int[] iarr = new int[LENGTH];

for (int i = 0; i < iarr.length; i++) {

//iarr[i] = rand.nextInt(99999999);

}

*/

int[] iarr = {51, 13, 25, 73, 59, 53, 81, 92, 64, 39, 33, 38};

//System.out.println("Initial array:");

//displayArray(iarr, 0, iarr.length-1);

int[] aux = new int[iarr.length]; // make an auxiliar array to improve speed

mergesort(iarr, aux, 0, iarr.length-1);

//System.out.println("Sorted Array:");

//displayArray(iarr, 0, iarr.length-1);

}

private static void mergesort(int[] data, int[] aux, int begin, int end) {

if (end <= begin)

return;

int middle = begin + (end - begin) / 2;

mergesort(data, aux, begin, middle);

mergesort(data, aux, middle+1, end);

merge(data, aux, begin, middle, end);

displayArray(data, 0, data.length-1);

}

private static void merge(int[] data, int[] aux, int begin, int middle, int end) {

//copy to auxiliar array

for (int k = begin; k <= end; k++)

aux[k] = data[k];

int i = begin;

int j = middle + 1;

for (int k=begin; k<=end; k++) {

if (i > middle)

data[k] = aux[j++];

else if (j > end)

data[k] = aux[i++];

else if (aux[j] < aux[i])

data[k] = aux[j++];

else

data[k] = aux[i++];

}

}

private static void displayArray(int[] data, int start, int end) {

for (int i = start; i <= end; i++) {

System.out.print(data[i] + " ");

}

System.out.println();

}

}