Thread: counting number of comparisons in merge sort

guys, I have the following merge sort algorithm, and I'm trying to count the number of comparison that is has to do in order to sort the whole array. I know the formula, I just don't know where to put the counter since it is a recursive algorithm... could someone shed some light on this. Thanks

//sorting array using merge sort
    static void mergeSort(int[] a)
    {
        if(a.length > 2)
        {
            int mid = a.length / 2;
            int[] first = new int[mid];
            int[] second = new int[a.length - mid];
 
            for(int i = 0; i < first.length; i++) { first[i] = a[i]; }
            for(int i = 0; i < second.length; i++)
            {
                second[i] = a[mid+i];
            }
            mergeSort(first);
            mergeSort(second);
            merge(first, second, a);
        }
    }
 
    //merging first and second halfs of mergeSort array
    static void merge(int[] first, int[] second, int[] a)
    {
        int iFirst = 0;
        int iSecond = 0;
        int i = 0; 
        //moving the smaller element into a
        while(iFirst < first.length && iSecond < second.length)
        {
            if(first[iFirst] < second[iSecond])
            {
                a[i] = first[iFirst];
                iFirst++;
            }
            else
            {
                a[i] = second[iSecond];
                iSecond++;
            } 
            i++;
            mergeCounter += i;
        }
        //copying the remaning of the first array
        while(iFirst < first.length)
        {
            a[i] = first[iFirst];
            iFirst++; i++;
        }
        //copying the remaining of second array
        while(iSecond < second.length)
        {
            a[i] = second[iSecond];
            iSecond++; i++;
        }        
    }

Hello mia_tech!
If I'm getting it right you are trying to count how many times executes the first while loop of merge. If you want to count it every time that merge is called you can have a local variable inside the method that does this. For example

static void merge(int[] first, int[] second, int[] a){       
        int mergeCounter = 0;
 
        while(...){          
            i++;          
        }
        mergeCounter += i; //you have to increment the variable AFTER the loop has exit 
}

If you want to count it in a whole mergesort proccess then you should declare mergeCounter as a global variable. For example

 
class MergeSort{
 
   static int mergeCounter = 0;
 
   static void mergeSort(int[] a){
 
   }
 
   static void merge(int[] first, int[] second, int[] a){      
        while(...){        
            i++;         
        }
        mergeCounter += i; //you have to increment the variable AFTER the loop has exit           
   }
}

Hope this helps.

Cannot test the code right now but I think the problem with your code is that you add i to the counter in every iteration. See the following example:
1st iteration: i = 1 , counter = 1;
2nd iteration: i = 2 , counter = 3 (1+2)
3rd iteration: i = 3 , counter = 6 (3+3).
So, in three iterations (which is what you want to count) the counter is six when actually the comparisons are 3.
The actual number of the comparisons is i. Therefore you should add i after the loop (when it has its last value).
Hope I was clear.

Originally Posted by andreas90

Cannot test the code right now but I think the problem with your code is that you add i to the counter in every iteration. See the following example:
1st iteration: i = 1 , counter = 1;
2nd iteration: i = 2 , counter = 3 (1+2)
3rd iteration: i = 3 , counter = 6 (3+3).
So, in three iterations (which is what you want to count) the counter is six when actually the comparisons are 3.
The actual number of the comparisons is i. Therefore you should add i after the loop (when it has its last value).
Hope I was clear.

if you take a look at mergeSort method it has two recursive calls in it, so every time merge is called it reset i = 0, so you need some sort of class variable to keep track of total i's

Originally Posted by mia_tech

if you take a look at mergeSort method it has two recursive calls in it, so every time merge is called it reset i = 0, so you need some sort of class variable to keep track of total i's

Exactly, this is what I suggested you with the second code of post#2. Did you try it?
In post#4 I only explained why you need to put the mergeCounter += i; statement after the while loop and not inside it.

I think you might be right ;0)

ok, I forgot that 25 is worst case scenario in which you need to compare all numbers, but here are the numbers I'm comparing. could you tell me what's the number of comparison you get

45 62 98 89 47 59 72 82 45 18

Thanks

Originally Posted by mia_tech

ok, I forgot that 25 is worst case scenario in which you need to compare all numbers, but here are the numbers I'm comparing. could you tell me what's the number of comparison you get

45 62 98 89 47 59 72 82 45 18

Thanks

the answer is 23 for this array