title: Java - Mergesort counting
body: <p>I have made a mergesort that is being juxtaposed with two already created selection and insertion sorts which both count the comparisons so that when executed the program illustrates which methods are faster.</p>
  
  <ol>
  <li>I can't figure out how to get a count implemented into my mergeset   </li>
  <li>I really don't know if it's even working correctly or if I'm just displaying a previously already sorted array, that was sorted by selection or insertion above it. I think this because I wasn't able to call the method how the selection and insertion were. (You'll see below)</li>
  </ol>
  
  <p>I'll post full code so far so you can see selection and insertion, how they were used.</p>
  
  <p>Arraysort.java</p>
  
  <hr>
  
  <pre><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&lt;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&gt;0) {
             count++;                       // count next comparison
             if (a[n-1] &gt; 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&lt;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 &gt; 0; out--) {  // outer loop
           max = out;                        // max is maximum item's index
           for(in=0; in&lt;out; in++) {          // inner loop
              if(a[in] &gt; 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 void mergeSort() {
         long[] ws = new long[nElems];
         recMergeSort(ws, 0, nElems-1);
     }
  
     public void recMergeSort(long[] ws, int lower, int upper) {
         if (lower == upper)
             return;
         else {
             int mid = (lower + upper) / 2;    //find midpoint
             recMergeSort(ws, lower, mid);    //sort lower
             recMergeSort(ws, mid+1, upper);    //sort upper
             merge(ws, lower, mid+1, upper);    //merge
         }
  
     }
  
     public void merge(long[] ws, int lowPtr, int highPtr, int upper) {
         int j = 0;
         int lower = lowPtr;
         int mid = highPtr-1;
         int n = upper-lower+1;        //# of items
  
         while(lowPtr &lt;= mid &amp;&amp; highPtr &lt;= upper)
               if( a[lowPtr] &lt; a[highPtr] )
                  ws[j++] = (int) a[lowPtr++];
               else
                  ws[j++] = (int) a[highPtr++];
  
            while(lowPtr &lt;= mid)
               ws[j++] = (int) a[lowPtr++];
  
            while(highPtr &lt;= upper)
               ws[j++] = (int) a[highPtr++];
  
            for(j=0; j&lt;n; j++)
               a[lower+j] = ws[j];
  
     }
  
     public void display() {
         for(int j=0; j&lt;nElems; j++) {
             System.out.print(a[j] + " "); }
         System.out.println("");
         }
  
  
  //end
  }  
  </code></pre>
  
  <hr>
  
  <p>SortComparison.java</p>
  
  <pre><code>import java.util.*;
  
  public class SortComparison {
  
     public static void main(String[] args) {
  
        int count, maxSize = 100;      // 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 &lt; 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("\nInsert sort: \n" + carr + " ### Comparisons: " + count);                  
  
        arr.Clone(carr);
        count = carr.selectionSort();          // selection-sort a clone of arr
        System.out.println("\nSelect sort: \n" + carr + " ### Comparisons: " + count); 
  
        carr.mergeSort();
        System.out.println("\nMerge sort: ");
        carr.display();
  
  
  
   }
  
  }
  </code></pre>
  
  <hr>
  
  <p>You can see how things should be called, with the count returning, by selection and insertion..</p>