Question

   private static void merge(int arr[], int l, int m, int r) {
       // Find sizes of two subarrays to be merged
       int n1 = m - l + 1;
       int n2 = r - m;

       /* Create temp arrays */
       int L[] = new int[n1];
       int R[] = new int[n2];

       /* Copy data to temp arrays */
       for (int i = 0; i < n1; ++i)
           L[i] = arr[l + i];
       for (int j = 0; j < n2; ++j)
           R[j] = arr[m + 1 + j];

       /* Merge the temp arrays */

       // Initial indexes of first and second subarrays
       int i = 0, j = 0;

       // Initial index of merged subarry array
       int k = l;
       while (i < n1 && j < n2) {
           if (L[i] <= R[j]) {
               arr[k] = L[i];
               i++;
           } else {
               arr[k] = R[j];
               j++;
           }
           k++;
       }

       /* Copy remaining elements of L[] if any */
       while (i < n1) {
           arr[k] = L[i];
           i++;
           k++;
       }

       /* Copy remaining elements of R[] if any */
       while (j < n2) {
           arr[k] = R[j];
           j++;
           k++;
       }
   }

   /**
   * Merge sort
   *
   * @param arr - Integer array
   * @param l -Left index
   * @param r - right index
   */
   private static void mergeSort(int arr[], int l, int r) {
       if (l < r) {
           // Find the middle point
           int m = (l + r) / 2;

           // Sort first and second halves
           mergeSort(arr, l, m);
           mergeSort(arr, m + 1, r);

           // Merge the sorted halves
           merge(arr, l, m, r);
       }
   }

How to count number of swaps and comparisions in the above code?

Answer 1

We can see that both swap and comparison operations are happening in merge function. So we can create two global variable count_swaps and count_comparisons initialized to 0, and on every comparison the value of count_comparisons will increment by 1 and on every swap count_swaps will increment by 1.

We can keep the variable count_comparisons just below the while loop which is "while (i < n1 && j < n2)" , here every iteration of while loop is happen with one comparison and hence we increment count_comparisons on every iteration of while loop. Now swap happen if within this while loop i.e. "while (i < n1 && j < n2)" , whenever the if condition i.e.  "if (L[i] <= R[j])" is satisfied then L[i] will be placed before R[i] and swapping will not happen but if this condition is not satisfied then R[j] will placed before L[i] and hence swap happen, so increment the count_swaps by 1.

So below is the modification of while loop "while (i < n1 && j < n2)" inside which we increment both count_comparisons and count_swaps.

while (i < n1 && j < n2) {

count_comparisons++ ; //increment by 1
           if (L[i] <= R[j]) {
               arr[k] = L[i];
               i++;
           } else {

count_swaps++; //increment by 1
               arr[k] = R[j];
               j++;
           }
           k++;
       }

Hence at the end of algorithm value of count_swaps and count_comparisons will be desired answer.

Please comment for any clarification.