import java.util.*;
public class MergeSortIllustration
{
public static void mergeSort (int [] list, int first, int last)
{
// Algorithm:
// If list size > 1:
// 1. Mergesort each half of list (via a recursive call)
// 2. Merge two sorted halves
System.out.print("Calling mergeSort() on {");
for (int x : list)
{
System.out.print(" " + x + " ");
}
System.out.println("} with first: " + first + ", last: " + last + "\n");
if (first >= last)
{
// Do nothing;
System.out.println("The range has 1 or no elements; there's nothing to do here.\n");
}
else
{
int middle = (first + last) / 2;
mergeSort(list, first, middle);
mergeSort(list, middle+1, last);
merge(list, first, middle, middle+1, last);
System.out.println("\nAfter applying mergeSort with first: " + first + ", last: " + last + ":\n");
for (int x : list)
{
System.out.print(x + " ");
}
System.out.println();
}
}
private static void merge (int [] list, int f, int m, int n, int l)
{
// Merge two subarrays list[f-m] and list[n-l]
// Assume that m + 1 == n
System.out.println("Applying merge() to the range " + f + "-" + l + "...\n");
int [] temp = new int[(m - f) + (l - n) + 2];
int tempPos = 0;
int list1Pos = f;
int list2Pos = n;
while (list1Pos <= m && list2Pos <= l) // While both lists have data
{
System.out.println("Comparing " + list[list1Pos] + " and " + list[list2Pos]);
if (list[list1Pos] < list[list2Pos])
{
// Update list1Pos
temp[tempPos] = list[list1Pos];
list1Pos++;
}
else
{
temp[tempPos] = list[list2Pos];
list2Pos++;
}
tempPos++;
}
// One list has run out. We don't know which one
while (list1Pos <= m)
{
temp[tempPos] = list[list1Pos];
tempPos++;
list1Pos++;
}
while (list2Pos <= l)
{
temp[tempPos] = list[list2Pos];
tempPos++;
list2Pos++;
}
// Copy temp back to list
tempPos = 0;
for (int pos = f; pos <= l; pos++)
{
list[pos] = temp[tempPos];
tempPos++;
}
System.out.println("\nAfter merging from " + f + "-" + l + ":\n");
for (int x : list)
{
System.out.print(x + " ");
}
System.out.println();
}
}