2

I am working on evaluating the Merge Sort algorithm and counting the critical operations. While technically this is homework, it is from a prior assignment and the code is a scaled down version to only show the area in question. I am trying to better understand my issue and debug my critical operations count to be accurately portrayed.

The project was to implement Merge Sort and evaluate it. The area of concern is counting critical operations and determining the deviation of the count by randomly filling an array with 10 different sizes and each size ran 50 different times (with different random data). My findings were that for each size the number of critical operations always ended the same (e.g. array of size 10 came to 68 critical operations regardless of the data) leaving a critical operations deviation of 0.

The professor stated this was inaccurate and there was something wrong with my program as it should produce different counts for differing data for each array length. I am trying to figure out what in my program is inaccurate causing this issue. I have checked that each pass is producing different array data and that this data is being passed to the sorting algorithm and properly sorted.

Below is my code that I wrote that, again, regardless of the data it still produces the same critical operations count. Can anyone pin point my issue? Regardless of what I do to the count it always produces the same value.

public class MergeSortSingle {
public static int count = 0;

private MergeSortSingle() { }

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {

    // copy to aux[]
    for (int k = lo; k <= hi; k++) {
        count++;
        aux[k] = a[k]; 
    }

    // merge back to a[]
    int i = lo, j = mid+1;
    for (int k = lo; k <= hi; k++) {
        if      (i > mid) {
            count++;
            a[k] = aux[j++];
        }
        else if (j > hi) {
            count++;
            a[k] = aux[i++];
        }
        else if (less(aux[j], aux[i])) {
            count++;
            a[k] = aux[j++];
        }
        else      {
            count++;
            a[k] = aux[i++];
        }
    }
}

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
    if (hi <= lo) return;
    int mid = lo + (hi - lo) / 2;
    sort(a, aux, lo, mid);
    sort(a, aux, mid + 1, hi);
    merge(a, aux, lo, mid, hi);
}

public static void sort(Comparable[] a) {
    Comparable[] aux = new Comparable[a.length];
    sort(a, aux, 0, a.length-1);
}

private static boolean less(Comparable v, Comparable w) {
    return v.compareTo(w) < 0;
}

private static void show(Comparable[] a) {
    System.out.println("\nAfter Sorting completed:");
   System.out.print(Arrays.toString(a));
   System.out.println();
}

public static void main(String[] args) {
    int length = 10;
    Comparable[] a = new Comparable[length];
    for (int w = 0; w < length; w++) {
            a[w] = (int) (Math.random() * 10000 + 1);
        }
    System.out.println("Before Sorting:");
    System.out.print(Arrays.toString(a));
    System.out.println();
    MergeSortSingle.sort(a);
    show(a);
    System.out.println("\nCounter = " + count);
}
}

Sample Output 1:

Before Sorting: [9661, 4831, 4865, 3383, 1451, 3029, 5258, 4788, 9463, 8971]

After Sorting completed: [1451, 3029, 3383, 4788, 4831, 4865, 5258, 8971, 9463, 9661]

Counter = 68

Sample Output 2:

Before Sorting: [9446, 230, 9089, 7865, 5829, 2589, 4068, 5608, 6138, 372]

After Sorting completed: [230, 372, 2589, 4068, 5608, 5829, 6138, 7865, 9089, 9446]

Counter = 68

The merge sort code was utilized from: http://algs4.cs.princeton.edu/22mergesort/Merge.java.html

4
  • Has your professor defined what a critical operation is? The way you count them should lead to a completely deterministic value depending on the length of the array seeing how you increase the counter by 1 with each execution of the for loops. Commented Oct 15, 2016 at 12:17
  • The critical operations are either comparisons or assignments or both. Commented Oct 15, 2016 at 12:44
  • 1
    @fox.josh - Normally only comparisons of array data are counted as comparisons. Comparisons like i > mid or j > high are not counted as comparisons because they're used to copy data. In the case of arrays, these could be optimized with something like array copy. Despite that, there won't be a lot of difference in comparison counts with random data. There will be far fewer array data comparisons if the data is already sorted. For a basic merge sort, the number of moves is always the same. Commented Oct 15, 2016 at 15:26
  • @rcgldr - Thank you for the contribution. I have revised my critical operation counting. Commented Oct 15, 2016 at 16:21

1 Answer 1

1

You only counting while merging the sub-arrays - you use the counter for copying the array tro aux - that will always be the same number of operations, and then you use it again at the for loop - you have 4 paths there, and each of them increments the counter - again, a fixed number of times.
you have to count comarasions as well at sort - if (hi <= lo) - its an operations. If it fails - it's another operation.

Sign up to request clarification or add additional context in comments.

3 Comments

I have went as far as placing a counter increment on every line of code for both merge and sort methods and still it produces the same number each time. I have yet to find a placement that does produce differing outcomes over multiple passes.
Just as I submitted this comment I found my area of discrepancy. Placing a counter on the "less method", which is appropriate, gives me the differing count value that I was seeking. Thank you guys for the help.
private static boolean less(Comparable v, Comparable w) { count++; return v.compareTo(w) < 0; }

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.