Thread: displaying every 1000 comparisons in merge sort

gusy, I have the following merge sort algorithm, and if the number of comparisons is over 1000, I need to display every 1000th comparison, but in this case is kind of tricky since the merge sort is recursive... could anyone give me a hand on how to implement this... here's the code

//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++;             
        }
        counter += i;        
 
        //copying the remaining of 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++;
        }        
    }

Originally Posted by Norm

Can you show where in the code you are trying to display something?
How are you trying to detect the 1000th event?

I was thinking to implement a if statement right after counter that output to screen in increments of 1000, but it is not working, it outputs wired numbers, besides what if total comparisons are smaller than 1000.

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++;             
        }
        counter += i;  
        if(counter >= 1000 && counter % 1000 == 0)
            System.out.println(counter);
 
        //copying the remaining of 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++;
        }        
    }

ok, I got it.... is working now, but I have one more question, if I need to display the same for both selection sort and merge sort, wouldn't be better to create a method for that?

Originally Posted by Norm

What would the method do? Test a value and print a message?

test whether the number of comparison is over 1000, if it is then print every 1000th number, and then print the total number of comparisons