In section 14.5, we approximated a count of the array visits in merge sort. Your task is to provide an accurate measurement for the implementation used in section 15.4. Count each occurrence of a[i], first[i], or second[i] as a visit. When recursively generating smaller merge sorters, be sure to copy their visit counts after they have completed.

Complete the following file:

MergeSorter.java

/** 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; } /** Sorts the array managed by this merge sorter. */ public void sort() { // TODO: update visitCount if (a.length <= 1) return; int[] first = new int[a.length / 2]; int[] second = new int[a.length - first.length]; // Copy the first half of a into first, the second half into second for (int i = 0; i < first.length; i++) { first[i] = a[i]; } for (int i = 0; i < second.length; i++) { second[i] = a[first.length + i]; } 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) { // TODO: update visitCount // 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++; } 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++; } } public int getVisitCount() { return visitCount; } private int[] a; private int visitCount; // this method is used to check your work public static int check(int n) { int[] a = new int[n]; for (int i = 0; i < n / 2; i++) { a[i] = n - i; a[n - i - 1] = i + 1; } MergeSorter sorter = new MergeSorter(a); sorter.sort(); return sorter.getVisitCount(); } }