Merge Sort Comparison Counter

Question

I cant seem to figure out where to put my comparison counter in the Merge class. Although it sorts the array perfectly, it will not count the number of swaps (or comparisons) it made. Please help this is apart of my final project

      public static int mergeSort(int[] intArray, int first, int last) {
        if(first < last) {
          int mid = (first + last) / 2;
          mergeSort(intArray, first, mid);
          mergeSort(intArray, mid + 1, last);
          Merge(intArray, first, mid, last);

     }

     return comparisons;

  }

  public static int Merge(int[] intArray, int first, int mid, int last) {

     //int count = 0;
     comparisons = 0;
     int first1 = first, last1 = mid;
     int first2 = mid + 1, last2 = last;
     int temp[] = new int[intArray.length];
     int index = first1;

     while(first1 <= last1 && first2 <= last2) {
        if(intArray[first1] < intArray[first2]) {
           temp[index] = intArray[first1++];
           comparisons++;
        }
        else
            temp[index] = intArray[first2++];
            index++;
            comparisons++;
     }

     while(first1 <= last1)
        temp[index++] = intArray[first1++];

     while(first2 <= last2)
        temp[index++] = intArray[first2++];

     for(index = first; index <= last; index++)
        intArray[index] = temp[index];


     return comparisons;
  }

Answer 1

In the code you included here, you didn't show the definition of the variable comparisons, but since you're using it without defining it, I'm assuming it's a field in your class. If that's the case, I think the issue is this line in Merge:

comparisons = 0;

Since you have one global counter of the number of comparisons made, the presence of this line means that whenever you call Merge, you're resetting the total number of comparisons back to zero, even if in the course of executing mergesort you already have made a bunch of comparisons.

As a quick fix, just delete this line. However, I think you'd be better off fixing this by just not having this as a field at all and using return values to communicate back the number of comparisons made. Here's one way to do this:

  public static int mergeSort(int[] intArray, int first, int last) {
    int compares = 0;
    if(first < last) {
      int mid = (first + last) / 2;
      compares += mergeSort(intArray, first, mid);
      compares += mergeSort(intArray, mid + 1, last);
      compares += Merge(intArray, first, mid, last);

 }

 return compares;

}

public static int Merge(int[] intArray, int first, int mid, int last) { int comparisons = 0; int first1 = first, last1 = mid; int first2 = mid + 1, last2 = last; int temp[] = new int[intArray.length]; int index = first1;

 while(first1 <= last1 && first2 <= last2) {
    if(intArray[first1] < intArray[first2]) {
       temp[index] = intArray[first1++];
       comparisons++;
    }
    else
        temp[index] = intArray[first2++];
        index++;
        comparisons++;
 }

 while(first1 <= last1)
    temp[index++] = intArray[first1++];

 while(first2 <= last2)
    temp[index++] = intArray[first2++];

 for(index = first; index <= last; index++)
    intArray[index] = temp[index];


 return comparisons;

}