public static <T extends Comparable<? super T>> void iterativeMergeSort(T[] input)
{
// Create a temporary array for sorting
Class elementType = input.getClass().getComponentType();
T temp[] = (T[]) java.lang.reflect.Array.newInstance( elementType, input.length);
 
// Initialize variable to store size of segments
int size = 0;
mergePass(input, temp, size, input.length /2);
mergePass(input, temp, input.length /2, input.length -1);
}
 
public static <T extends Comparable<? super T>> void mergePass(T[] input, T[] temp, int size, int end)
{
// Initialize index of next segment
int indexNext = size;
while (indexNext < end)
{
//need to divide the array into two parts
merge(input, size, (indexNext + size + 1)/2 - 1, indexNext + 1,temp);
indexNext = indexNext+1;
}
for (int copy = size; copy < end; copy++)
{
temp[copy] = input [copy];
}
}
 
private static <T extends Comparable<? super T>> void merge (T[] a, int begin, int mid, int end, T[] tmp)
{
int i = begin; // keeps track of where I am in first half
int j = mid + 1; // keeps track of where I am in second half
int k = 0; // keeps track of where I am in merged list
 
while (i<=mid && j<=end) { // go while both halves have elements
if (a[i].compareTo(a[j]) < 0)
tmp[k++] = a[i++];
else
tmp[k++] = a[j++];
}
 
// copy the tail of the half that still has elements left
// only one of these two while loops will execute, b/c either i>mid or j>end
while ( j <= end )
tmp[k++] = a[j++];
while ( i <= mid )
tmp[k++] = a[i++];
 
// Copy tmp, which is sorted, back to a[begin..end]
for ( k = 0, i = begin; i <= end; k++, i++)
a[i] = tmp [k];
}