Recursive MergeSort and counting comparisons

Question

I have written a program that contains 4 sorting methods, selection sort, insertion sort, merge sort, and recursive merge sort. The insertion and selection sort methods run fine and return to me a sorted list and the right amount of comparisons. My merge sort method returns me a sorted list, but my comparisons = 1. My recursive merge sort doesnt even sort the list and also says comparisons = 1. Can anybody help me find my errors? Here is all my code.

public class ArraySort {
    private long[] a;                 // ref to array a
    private int nElems;               // number of data items

    public ArraySort(int max) {       // constructor
       a = new long[max];             // create the array
       nElems = 0;                    // no items yet
    }

    public void Clone(ArraySort c) {  // c is another array
       c.nElems = this.nElems;                                 // Copy nElems
       System.arraycopy(this.a, 0, c.a, 0, this.nElems);       // Copy elements
    }

    public void insert(long value) {  // put element into array
       a[nElems++] = value;           // insert value
    }

    public String toString() {           // displays array contents
       String res="";
       for(int j=0; j<nElems; j++)       // for each element,
          res = res + a[j] + " ";        // append it to res
       return res;
    }

    private int insertOrder(int n, long temp) { // insert temp into a[0..(n-1)]
                  // and keep a[0..n] sorted.
        int count = 0;
        while (n > 0) {
            count++;                       // count next comparison
            if (a[n-1] > temp)   {         // until one is smaller,
               a[n] = a[n-1];              // shift item to right
               --n;                        // go left one position
            } else break;
        }
        a[n] = temp;                      // insert marked item
        return count;
    }

    public int insertionSort() {
        int count = 0;
        for (int n=1; n<nElems; n++)  
            count += insertOrder(n, a[n]);   // insert a[n] into a[0..(n-1)]

        return count;
    } // end insertionSort()

    private void swap(int one, int two) {
       long temp = a[one];
       a[one] = a[two];
       a[two] = temp;
    }

    public int selectionSort() {
       int out, in, max, count=0;

       for(out=nElems-1; out > 0; out--) {  // outer loop
          max = out;                        // max is maximum item's index
          for(in=0; in<out; in++) {          // inner loop
             if(a[in] > a[max] )            // if max is smaller,
                 max = in;                  // we have a new max
             count++;                       // count one comparison
          }
          swap(out, max);                   // swap them
       }  // end for(out)
       return count;
    }  // end selectionSort()

    public int mergeSort() {           // called by main()
        int count = 0;
        long[] workSpace = new long[nElems]; // provides workspace
        recMergeSort(workSpace, 0, nElems-1);
        count++;
        return count;
    }


public int recMergeSort(long[] workSpace, int lowerBound,
        int upperBound) {

    int count = 0;

    if(lowerBound == upperBound)            // if range is 1,
        return 1;

    // find midpoint
    int mid = (lowerBound+upperBound) / 2;

    recMergeSort(workSpace, lowerBound, mid);   // sort low half

    recMergeSort(workSpace, mid+1, upperBound);  // sort high half


    merge(workSpace, lowerBound, mid+1, upperBound); // merge them
    count++;
    return count;

}  // end else
  // end recMergeSort()


private int merge(long[] workSpace, int lowPtr,
        int highPtr, int upperBound)
{
    int j = 0;                             // workspace index

    int lowerBound = lowPtr;

    int mid = highPtr-1;

    int n = upperBound-lowerBound+1;       // # of items

    int count = 0;

    while(lowPtr <= mid && highPtr <= upperBound)

        if( a[lowPtr] < a[highPtr] ) {
            workSpace[j++] = a[lowPtr++];
            count++;
        }

        else {
            workSpace[j++] = a[highPtr++];
            count++;
        }

        while(lowPtr <= mid)
            workSpace[j++] = a[lowPtr++];

        count++;


        while(highPtr <= upperBound)
            workSpace[j++] = a[highPtr++];

        count++;

        for(j=0; j<n; j++)

           a[lowerBound+j] = workSpace[j];

        return count;
    }  // end merge()
}

The methods are being called from here...

import java.util.*;

public class SortComparison {

    public static void main(String[] args) {

       int count, maxSize = 20;      // array size
       ArraySort arr, carr;           // reference to array
       arr = new ArraySort(maxSize);  // create the arrays
       carr = new ArraySort(maxSize);

       // insert some random numbers
              Random generator = new Random();
       for (int i = 0; i < 20; i++) {
            arr.insert(Math.abs(generator.nextInt())%maxSize);
       }

       System.out.println("Before sort: " + arr);                // display items

       arr.Clone(carr);
       count = carr.insertionSort();          // insertion-sort a clone of arr
       System.out.println("Insert sort: " + carr + " comparions=" + count);                  

       arr.Clone(carr);
       count = carr.selectionSort();          // selection-sort a clone of arr
       System.out.println("Select sort: " + carr + " comparions=" + count); 

       arr.Clone(carr);
       count = carr.mergeSort();
       System.out.println("Merge sort: " + carr + " comparions=" + count);

       arr.Clone(carr);
       count = carr.recMergeSort(null, maxSize, maxSize);
       System.out.println("RecMerge sort: " + carr + " comparions=" + count);

  }  // end main()

}  // end class SortComparison

and when the program is run this is the output i receive...

Before sort: 3 2 4 7 17 11 3 0 14 6 8 7 12 15 0 0 9 4 7 16 
Insert sort: 0 0 0 2 3 3 4 4 6 7 7 7 8 9 11 12 14 15 16 17  comparions=94
Select sort: 0 0 0 2 3 3 4 4 6 7 7 7 8 9 11 12 14 15 16 17  comparions=190
Merge sort: 0 0 0 2 3 3 4 4 6 7 7 7 8 9 11 12 14 15 16 17  comparions=1
RecMerge sort: 3 2 4 7 17 11 3 0 14 6 8 7 12 15 0 0 9 4 7 16  comparions=1

Can anybody help me fix this!?

Answer 1

I dont know why my recursive merge sort method wont sort the list. And why the comparisons = 1 for the last two.

Answer 2

Since it's a homework, I'll only show how to fix mergeSort():

public int mergeSort() {
    int count = 0;
    long[] workSpace = new long[nElems];
    count += recMergeSort(workSpace, 0, nElems-1); // Add the comparisons executed there
    return count;
}

You need to fix recMergeSort() in a similar fashion.

I guess that you think of count as of a global variable. But it's not. In all your sorting methods count is a local variable, which is not visible outside the scope of the method. Therefore, if you modify the count variable inside recMergeSort() it will not be automatically affect the (other) count variable inside mergeSort(). A natural way to "send" the count from (called) recMergeSort() to (calling) mergeSort() is through return count, as you correctly did. Unfortunately, you did not use the result which recMergeSort() returned.

One last thing, since maybe I wasn't clear enough: even if you recursively call recMergeSort() from recMergeSort(), still the count variable in the caller is different from the count variable in the callee. So even if you do recursive calls, still the called method needs to pass the result through return and the calling method needs to pick it up.

Answer 3

In the future, just post the relevant code. We don't necessarily need to see all the methods that work.

It is possible to make a recursive sort algorithm using only one method (and personally, I think it would be easier if you did). You're very much on the right track, at any rate. But look at mergeSort() - you declare count = 0, do your recursion, add 1 to count, and then return it. The problem you're having is that you only increment count once, when you should be giving it the value returned by recMergeSort(). See my in-line comments for solutions.

public int mergeSort() {           // called by main() 
    int count = 0;

    long[] workSpace = new long[nElems]; // provides workspace
        /*
           recMergeSort() returns an integer, but you do not assign it to anything.
        */
    recMergeSort(workSpace, 0, nElems-1);
    count++;
        /* Instead, try something like 
               count = recMergeSort(workspace, 0, nElms-1);
               return count;
        */
return count;
}


public int recMergeSort(long[] workSpace, int lowerBound, int upperBound) { int count = 0;
    if(lowerBound == upperBound) // if range is 1, return 1;
    // find midpoint int mid = (lowerBound+upperBound) / 2;
    recMergeSort(workSpace, lowerBound, mid); // sort low half
    recMergeSort(workSpace, mid+1, upperBound); // sort high half
    merge(workSpace, lowerBound, mid+1, upperBound); // merge them count++; return count; } // end else // end recMergeSort()
    private int merge(long[] workSpace, int lowPtr, int highPtr, int upperBound) { int j = 0; // workspace index
    int lowerBound = lowPtr;
    int mid = highPtr-1;
    int n = upperBound-lowerBound+1; // # of items
    int count = 0;
    while(lowPtr <= mid && highPtr <= upperBound)
    if( a[lowPtr] < a[highPtr] ) {
        workSpace[j++] = a[lowPtr++];
        count++;
    } else {
        workSpace[j++] = a[highPtr++];
        count++; }
    while(lowPtr <= mid)
        workSpace[j++] = a[lowPtr++];
        count++;
    while(highPtr <= upperBound)
        workSpace[j++] = a[highPtr++];
        count++;
    for(j=0; j


                       //AAAAAH! What happened to your For loop???

        a[lowerBound+j] = workSpace[j]; return count; } // end merge()

}

Answer 4

The following is your mergeSort() method:

public int mergeSort() {           // called by main()
    int count = 0;
    long[] workSpace = new long[nElems]; // provides workspace
    recMergeSort(workSpace, 0, nElems-1);
    count++;
    return count;
}

This method returns 1 because you create a variable called count, increment it once and only once after calling recMergeSort, and then return it. recMergeSort contains another local variable called count, but this local variable is completely separate to that in mergeSort. The count++ lines in recMergeSort have no effect on count within mergeSort.

Your merge and recMergeSort methods both return the number of comparisons made, but you don't do anything with the returned values. To count the total number of comparisons, get rid of the count++ line in the above, and replace the line

recMergeSort(workSpace, 0, nElems-1);

with

count += recMergeSort(workSpace, 0, nElems-1);

You will also need to make similar changes to the various method calls in recMergeSort.

Why is the last line of your output above not sorting the list? Well, you are making the following method call:

count = carr.recMergeSort(null, maxSize, maxSize);

Your recMergeSort method begins as follows:

public int recMergeSort(long[] workSpace, int lowerBound,
        int upperBound) {

    int count = 0;

    if(lowerBound == upperBound)            // if range is 1,
        return 1;

    // rest of method omitted
}

You are clearly calling recMergeSort with the lowerBound and upperBound parameters the same. As a result, the method is returning 1, because you explicitly asked it to.