class MergeSort {
public static void main(String[] args) {
Integer[] arr = new Integer[] { 1, 6, -7, 8, 9};
for(Integer i : arr)
System.out.print(i + ", ");
System.out.println();
mergeSort(arr, 0, arr.length);
for(Integer i : arr)
System.out.print(i + ", ");
}
public static void mergeSort(Comparable[] arr, int from, int to)
{
if(to - from < 2)
{
if(arr.length != 1)
{
//swtich elements if not in natural ordering
if(arr[from].compareTo(arr[to - 1]) < 0)
{
Comparable temp = arr[from];
arr[from] = arr[to - 1];
arr[to - 1] = temp;
}
}
}
else
{
// DIVIDE and CONQUER
int middle = (to + from) / 2;
mergeSort(arr, from, middle);
mergeSort(arr, middle, to);
// MERGE
// -------------------------------------------------
Comparable[] tempArr = new Comparable[to - from];
int i = from;
int j = middle;
int k = 0;
// pick elements of arrays treated as stacks and put in the new array
while(i < middle && j < to)
{
if (arr[i].compareTo(arr[j]) < 0)
{
tempArr[k] = arr[i];
i++;
}
else
{
tempArr[k] = arr[j];
j++;
}
k++;
}
// add remaining elements from parts of array
while(i < middle)
{
tempArr[k] = arr[i];
i++;
k++;
}
while(j < to)
{
tempArr[k] = arr[j];
j++;
k++;
}
// merge temp array back into working array
for(int l = 0; l < tempArr.length; l++)
{
arr[from + l] = tempArr[l];
}
}
}
}
