COP 3337
  Section U05
  Spring 2017



                             MERGE SORT
                             ==========


      Below is a merge sort program. 

  I. The Driver, the program, and the print method:
  --------------------------------------------------

  public class MergeSort 
  {
      // test merge sort
      public static void main(String[] args) 
      {
          System.out.println("Test Merge Sort");
          System.out.println("===============");
        
          // the array to be sorted
          int[] table = { 78, 45, 89, 23, -26, -10, 37, 38, 47, 58, 69, -45, 4};
          printArray("The array before merge sort:",table);
          sort(table);
          System.out.println("We merge sort the array");
          printArray("The sorted array:", table);
      }
    
      // sort arr in increasing order using merge sort
      public static void sort(int[] arr)
      {
          if (arr == null || arr.length <= 1)
              return; // arr is sorted
          // arr has 2 or more integers.
          // split the array into 2 halves
          int[] first = new int[arr.length/2];
          int[] second = new int[arr.length - first.length];
          // copy the 2 halves of arr onto the first and second
          System.arraycopy(arr, 0, first, 0, first.length);
          System.arraycopy(arr, first.length, second, 0, second.length);
        
          // recursivery sort the 2 halves
          sort(first);
          sort(second);
          // merge the 2 sorted halves onto arr
          merge(first, second, arr);
      }        
    
      // merge the 2 sorted arrays arr1 and arr2 onto arr
      // it is assumed that neither one of the 3 is null, arr1 and arr2
      // have at least one item and arr.length >= arr1.length + arr2.length
      private static void merge (int[] arr1, int[] arr2, int[] arr)
      {
          // we compare the lowest items that were not processed of arr1 and
          // arr2 and enter the lowest in arr.
          // i is points to the lowest of arr1, j to the lowest of arr2, and
          // k is the position of arr that is going to be filled
        
          // loop until one of the 2 arrays is exhausted
          int i = 0, j = 0, k =0; 
          while (i < arr1.length && j < arr2.length )
              // compare arr1[i] and arr2[j]
              if (arr1[i] < arr2[j])
                  arr[k++] = arr1[i++];
              else // enter from arr2
                  arr[k++] = arr2[j++];
          // copy the rest of the remaining data 
          System.arraycopy(arr1,i,arr,k,arr1.length -i);
          System.arraycopy(arr2,j,arr,k,arr2.length -j);
      }   
    
      // print an array of integers, one per line
      // message is the header
      private static void printArray(String message, int[] arr)
      {
          // print the header and underline it
          System.out.println(message);
          for (int i = 0; i < message.length() ; i++)
              System.out.print('-');
          System.out.println();
        
          // check for null or emmpy array
          if (arr == null)
              System.out.println("Null array");
          else if (arr.length == 0)
              System.out.println("Empty array");
          else
          {
              for (int curr : arr)
                  System.out.println(curr);
          }    
      } // end printArray    
  }

  II. The output:
  ---------------

  run:
  Test Merge Sort
  ===============
  The array before merge sort:
  ----------------------------
  78
  45
  89
  23
  -26
  -10
  37
  38
  47
  58
  69
  -45
  4
  We merge sort the array
  The sorted array:
  -----------------
  -45
  -26
  -10
  4
  23
  37
  38
  45
  47
  58
  69
  78
  89
  BUILD SUCCESSFUL (total time: 0 seconds)