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
critical operationis? 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.