Please add a counter to the MergeSorter program to measure the number of comparisons of array elements being made while the routine is completing the sort.

private static void merge(int[] first, int[] second, int[] a) { 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 is 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++; } else { a[j] = second[iSecond]; iSecond++; } j++; } // Note that only one of the two loops below copies entries // Copy any remaining entries of the first array while (iFirst < first.length) { a[j] = first[iFirst]; iFirst++; j++; } // Copy any remaining entries of the second half while (iSecond < second.length) { a[j] = second[iSecond]; iSecond++; j++; } }

The behavior we want to monitor occurs in this section of code,

if (first[iFirst] < second[iSecond]) { a[j] = first[iFirst]; iFirst++; } else { a[j] = second[iSecond]; iSecond++; }

It is in the above section that we compare array elements and decide which element becomes part of our merged and sorted array. By counting the number of comparisons here, we obtain a measurement that helps us gauge the speed of the algorithm. Add code that will count each comparison, maintaining the result in an integer counter. Supply a method getCounter to retrieve the counter. Supply a second method called resetCounter to set the counter to 0.

The code below supports creating and swapping elements in arrays of varying sizes.

/** This class contains utility methods for array manipulation. */ public class ArrayUtil { /** Creates an array filled with random values. @param length the length of the array @param n the number of possible random values @return an array filled with length numbers between 0 and n - 1 */ public static int[] randomIntArray(int length, int n) { int[] a = new int[length]; for (int i = 0; i < a.length; i++) { a[i] = (int) (Math.random() * n); } return a; } /** Swaps two entries of an array. @param a the array @param i the first position to swap @param j the second position to swap */ public static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } }

Modify the main program below so we can test sorting arrays with sizes 10000, 20000, ,90000.

/** This program demonstrates the merge sort algorithm by sorting an array that is filled with random numbers. */ public class MergeSortDemo { public static void main(String[] args) { int[] a = ArrayUtil.randomIntArray(10000, 10000); MergeSorter.resetCounter(); MergeSorter.sort(a); System.out.println("Array size: 10000; comparisons: " + MergeSorter.getCounter()); } }

What are the results?

1) Modified Mergesorter class

2) Modified MergeSortDemo class

3) Results