Merge Sort count number of swaps and compares

Question

I have this existing code that I need to add a swap and compare counter for. So far I believe I have the counts correctly however I cannot get the output to no display a loop of each swap.

public void mergeSort(int[] a, int howMany) {


    if (a.length >= 2) {
        // split array into two halves
        int[] left  = Arrays.copyOfRange(a, 0, a.length/2);
        int[] right = Arrays.copyOfRange(a, a.length/2, a.length);


        // sort the two halves
        mergeSort(left,howMany);
        mergeSort(right, howMany);

        // merge the sorted halves into a sorted whole
        merge(a, left, right);

    }
}




// Merges the left/right elements into a sorted result.
// Precondition: left/right are sorted
public static void merge(int[] result, int[] left, 
                                       int[] right) {
    int i1 = 0;   // index into left array
    int i2 = 0;   // index into right array
   int compCount = 0;
   int swapCount = 0;  
    for (int i = 0; i < result.length; i++) {
        compCount++;
        if (i2 >= right.length ||
           (i1 < left.length && left[i1] <= right[i2])) {
            result[i] = left[i1];    // take from left
            i1++;
           swapCount++;
        } else {
            result[i] = right[i2];   // take from right
            i2++;
           swapCount++;
        }
    }
   //figure this loop issue out System.out.println("merge sort " + compCount + " " + swapCount);
}

Answer 1

I think the most elegant solution is to simulate pass-by-reference by using an int wrapper class. Everything in Java is pass-by-value, but if you don't change the reference that an Object reference points to, you can simulate pass-by-reference for recursive calls.

Here is an example:

import java.util.Arrays; 

public class TestMain
{
  public static void main(String[] args)
  {
    int[] array = new int[]{6, 2, 1, 4, 5, 3};

    IntWrapper countCompare = new IntWrapper();
    IntWrapper countSwap = new IntWrapper();



    MergeSort mSort = new MergeSort();

    mSort.mergeSort(array, countCompare, countSwap);

    System.out.println("Compares: " + countCompare.val);

    System.out.println("Swaps: " + countSwap.val);

    for (int i = 0; i < array.length; i++){
        System.out.print(String.format("%-3d", array[i]));
    }
  }


}

public class IntWrapper{
   int val = 0; 
}

public class MergeSort
{


    public void mergeSort(int[] a, IntWrapper compares, IntWrapper swaps) {


      if (a.length >= 2) {
          // split array into two halves
          int[] left  = Arrays.copyOfRange(a, 0, a.length/2);
          int[] right = Arrays.copyOfRange(a, a.length/2, a.length);


          // sort the two halves
          mergeSort(left, compares, swaps);
          mergeSort(right, compares, swaps);

          // merge the sorted halves into a sorted whole
          merge(a, left, right, compares, swaps);

      }
  }




  // Merges the left/right elements into a sorted result.
  // Precondition: left/right are sorted
  public static void merge(int[] result, int[] left, int[] right, IntWrapper compares, IntWrapper swaps) {
      int i1 = 0;   // index into left array
      int i2 = 0;   // index into right array
     //int compCount = 0;
     //int swapCount = 0;  
      for (int i = 0; i < result.length; i++) {
          //compCount++;
          compares.val++;
          if (i2 >= right.length ||
             (i1 < left.length && left[i1] <= right[i2])) {
              result[i] = left[i1];    // take from left
              i1++;
             //swapCount++;
             swaps.val++;
          } else {
              result[i] = right[i2];   // take from right
              i2++;
             //swapCount++;
             swaps.val++;
          }
      }
     //figure this loop issue out System.out.println("merge sort " + compCount + " " + swapCount);
  }
}

Output:

Compares: 16
Swaps: 16
1  2  3  4  5  6  

Answer 2

Make a global variable or a field within the class which holds the merge and merge sort methods. This will allow the methods to increment to the variable. If you declare inside the method it will stay as a local variable and each recursive call will produce different local variables of the same name but belonging to the different recursive method calls. Therefore your code should look like:

public class ClassWithMergeMethodInside
{
    int swapCount;
    int compCount;

    public void mergeSort(int[] a, int howMany) {
        //Since merge sort begins here you may initiliaze the variables here
        swapCount = 0;
        compCount = 0;
        if (a.length >= 2) {
            // split array into two halves
            int[] left  = Arrays.copyOfRange(a, 0, a.length/2);
            int[] right = Arrays.copyOfRange(a, a.length/2, a.length);


            // sort the two halves
            mergeSort(left,howMany);
            mergeSort(right, howMany);

            // merge the sorted halves into a sorted whole
            merge(a, left, right);

        }
    }




    // Merges the left/right elements into a sorted result.
    // Precondition: left/right are sorted
    public static void merge(int[] result, int[] left, 
                                           int[] right) {
        int i1 = 0;   // index into left array
        int i2 = 0;   // index into right array
        //Will not declare counter variables here
        for (int i = 0; i < result.length; i++) {
            compCount++;
            if (i2 >= right.length ||
               (i1 < left.length && left[i1] <= right[i2])) {
                result[i] = left[i1];    // take from left
                i1++;
               swapCount++;
            } else {
                result[i] = right[i2];   // take from right
                i2++;
               swapCount++;
            }
        }
       //figure this loop issue out System.out.println("merge sort " + compCount + " " + swapCount);
    }
}