CODEWITHSUNDEEP
javamergesort
user1832333
user1832333

Reputation:

Counting Number of Comparisons for MergeSort Java

I am having trouble counting the number of comparisons for mergesort in Java. Below is my code. Not sure if I'm placing it in the wrong spot, etc.

Any help is definitely appreciated, thanks.

private static int merge(int[] intArray, int first, int n1, int n2) {
    int numComparisons = 0;
        int[] temp = new int[n1+n2];
        int copied = 0, copied1 = 0, copied2 = 0;
        while((copied1 < n1) && (copied2 < n2)){
            if (intArray[first + copied1] < intArray[first + n1 + copied2]) {
                temp[copied++] = intArray[first + copied1++];
            }
            else {
                temp[copied++] = intArray[first + n1 + copied2++];
            }

        }

        while(copied1 < n1)     {
            temp[copied++] = intArray[first + copied1++];
        }
        while(copied2 < n2)     {
            temp[copied++] = intArray[first + n1 +copied2++];
        }


        for(int i = 0; i < n1+n2; i++) {
            numComparisons++;
            intArray[first + i] = temp[i];  
        }

        return numComparisons;
    }


    public static int mergeSortComparisons(int[] intArray, int first, int last){
        int n1, n2;
        if (last > 1){

            n1 = last/2;
            n2 = last - n1;

            mergeSortComparisons(intArray, first, n1);
            mergeSortComparisons(intArray, first + n1, n2);

            merge(intArray, first, n1, n2);
        }

        return first;
    }

Upvotes: 1

Views: 1642

Answers (1)

Eric Jablow
Eric Jablow

Reputation: 7899

If you want to count the number of comparisons, take the comparison step, refactor it to a method, and instrument the method. You are incrementing numComparisons in the wrong place.

private static boolean lessThan(int[] ia, int leftIndex, int rightIndex) {
    numComparisons++;
    return ia[leftIndex] < ia[rightIndex];
}

Use that instead of your comparison line near the top of merge.

Also, write JUnit tests to ensure that your sort works. Finally, do you need to have all your methods be static?

Upvotes: 1

Related Questions