Count++ wont add up

[sam8]

Hi guys,

I'm trying to count the comparisons in the mergesort algorithm so that I can compare it to other sorting algorithms. I've managed to get a count to work for insertsort but mergesort is being a complete pain!
It's probably a very simple problem but I've experimented around with it and can't get it to work.
I've got an integer (count1) to count comparisons within the mergesort method and then I want to print out the total number of comparisons, however, when the method is called, the output repeats the system.out.println on multiple lines, not adding up the seperate comparisons. The System.out.println("comparisons:" + count1 ); is getting stuck in a loop.
Can someone please tell me what I've done wrong??

Many thanks!

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package insertsort;
 import java.util.Random;
/**
 *
 * @author sam
 */
public class  MergeSort1 {
  private long[] theArray;

  private int nElems;
 public int count1=0;



  public MergeSort1(int max) {
    theArray = new long[max];
    nElems = 0;

  }

  public void insert(long value) {
    theArray[nElems] = value; // insert it
    nElems++; // increment size
  }

  public void display() {
    for (int j = 0; j < nElems; j++)
      System.out.print(theArray[j] + " ");
    System.out.println("");
  }

  public void mergeSort() {
    long[] workSpace = new long[nElems];
    recMergeSort(workSpace, 0, nElems - 1);
  }

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

      if (lowerBound == upperBound) // if range is 1,
      return; // no use sorting
    else { // find midpoint
      int mid = (lowerBound + upperBound) / 2;
      // sort low half
      recMergeSort(workSpace, lowerBound, mid);
      // sort high half
      recMergeSort(workSpace, mid + 1, upperBound);
      // merge them
      merge(workSpace, lowerBound, mid + 1, upperBound);


    }
  }

  private void 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


    while (lowPtr <= mid && highPtr <= upperBound)
    {
      if (theArray[lowPtr] < theArray[highPtr])
      {workSpace[j++] = theArray[lowPtr++];
      count1++;
      }
      else
      { workSpace[j++] = theArray[highPtr++];
         count1++;
      }
    while (lowPtr <= mid)
    { workSpace[j++] = theArray[lowPtr++];
        count1++;
    }
    while (highPtr <= upperBound)
    { workSpace[j++] = theArray[highPtr++];
        count1++;
    }
    for (j = 0; j < n; j++)
    {theArray[lowerBound + j] = workSpace[j];
    }

  }
    System.out.println("comparisons:" + count1);
  }

  public static void main(String[] args)

{

      int maxSize = 500; // array size

ArrayIns arr; // reference to array
arr = new ArrayIns(maxSize);
// create the array

 Random generator = new Random();

int i;


  MergeSort1 marr = new MergeSort1(maxSize); // create the array

    for(i=0; i<maxSize;i++)
{

marr.insert( generator.nextInt( 9999)); // insert 10 items

}


    System.out.println("");
    System.out.println("sorting items with merge sort...");

      marr.mergeSort();
  }
}

[moutanna]

you privide no information about ArrayIns.

[sam8]

you privide no information about ArrayIns.

sorry forgot to take that out, this was an extract from the longer program I was using for both insertsort and mergesort.

Any thoughts on why this count keeps repeating and doesn't add up though?

Thanks.