/**
This class sorts an array, using the merge sort algorithm.
*/
public class MergeSorter
{
/**
Constructs a merge sorter.
@param anArray the array to sort
*/
public MergeSorter(int[] anArray)
{
a = anArray;
c = 0;
}
/**
Sorts the array managed by this merge sorter.
*/
public void sort()
{
if (a.length <= 1) return;
int[] first = new int[a.length / 2];
int[] second = new int[a.length - first.length];
System.arraycopy(a, 0, first, 0, first.length);
System.arraycopy(a, first.length, second, 0, second.length);
MergeSorter firstSorter = new MergeSorter(first);
MergeSorter secondSorter = new MergeSorter(second);
firstSorter.sort();
secondSorter.sort();
merge(first, second);
}
/**
Merges two sorted arrays into the array managed by this
merge sorter.
@param first the first sorted array
@param second the second sorted array
*/
private void merge(int[] first, int[] second)
{
// Merge both halves into the temporary array
int iFirst = 0;
// Next element to consider in the first array
int iSecond = 0;
// Next element to consider in the second array
int j = 0;
// Next open position in a
// As long as neither iFirst nor iSecond past the end, move
// the smaller element into a
while (iFirst < first.length && iSecond < second.length)
{
if (first[iFirst] < second[iSecond])
{
a[j] = first[iFirst];
iFirst++;
c++;
}
else
{
a[j] = second[iSecond];
iSecond++;
c++;
}
j++;
}
// Note that only one of the two calls to arraycopy below
// copies entries
// Copy any remaining entries of the first array
System.arraycopy(first, iFirst, a, j, first.length - iFirst);
// Copy any remaining entries of the second half
System.arraycopy(second, iSecond, a, j, second.length - iSecond);
}
public int counter()
{
return c;
}
private int c;
private int[] a;
}
import java.util.Scanner;
public class Tester
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
System.out.print("Number of elements in the array? ");
int n = in.nextInt();
if (n < 0)
{
IllegalArgumentException exception = new IllegalArgumentException
("not below zero fool");
throw exception;
}
int[] a = new int[n];
for(int i = n; i > 0; i--)
{
a[i-1] = i;
}
MergeSorter b = new MergeSorter(a);
b.sort();
System.out.println("It took " + b.counter() + " comparisons");
}
}