Merge sort comparisons?
I don't think the number of comparisons using merge sort is correct in my
merge sort 2 class/method that returns the number of comparisons. Below is
my demo, I have an array of 4 integers 2,55,1,45 and when I run the
program it returns 8 comparisons. Can anyone verify if this correct or
what I am doing wrong?
My demo:
ArrayInts[] myInts2 = new ArrayInts[4];
myInts2[0] = new ArrayInts(2);
myInts2[1] = new ArrayInts(55);
myInts2[2] = new ArrayInts(1);
myInts2[3] = new ArrayInts(45);
MergeSort.mergeSort(myInts2, 0, 3);
System.out.println("Sorted using Merge Sort: ");
for (int index = 0; index < myInts2.length; index++) {
System.out.println(myInts2[index]);
}
System.out.println("Number of comps using Merge Sort: " +
MergeSort2.mergeSort2(myInts2, 0, 3));
System.out.println(" ");
My merge sort 2 class/method:
public class MergeSort2 {
private static long comp=0;
public static <T extends Comparable<? super T>> long mergeSort2(T[] data,
int min, int max) {
T[] temp;
int index1, left, right;
//return on list of length one
if (min == max) {
return comp;
}
//find the length and the midpoint of the list
int size = max - min + 1;
int pivot = (min + max) / 2;
temp = (T[]) (new Comparable[size]);
mergeSort2(data, min, pivot); //sort left half of list
mergeSort2(data, pivot + 1, max); //sort right half of list
//copy sorted data into workspace
for (index1 = 0; index1 < size; index1++) {
temp[index1] = data[min + index1];
}
//merge the two sorted lists
left = 0;
right = pivot - min + 1;
for (index1 = 0; index1 < size; index1++) {
comp++;
if (right <= max - min) {
if (left <= pivot - min) {
if (temp[left].compareTo(temp[right]) > 0) {
data[index1 + min] = temp[right++];
} else {
data[index1 + min] = temp[left++];
}
} else {
data[index1 + min] = temp[right++];
}
} else {
data[index1 + min] = temp[left++];
}
}
return comp;
}
}