/**
   *  Takes in entire vector, but will merge the following sections
   *  together:  Left sublist from a[first]..a[mid], right sublist from
   *  a[mid+1]..a[last].  Precondition:  each sublist is already in
   *  ascending order
   *
   * @param  a      reference to an array of integers to be sorted
   * @param  first  starting index of range of values to be sorted
   * @param  mid    midpoint index of range of values to be sorted
   * @param  last   last index of range of values to be sorted
   */
    public void merge(ArrayList<Comparable>a, int first, int mid, int last)
    {
        ArrayList<Comparable> temp = new ArrayList <Comparable>(a);
        int thing_a = first;
        int thing_b = mid + 1;
  
        for (int i = first; i <= last; i++)
        {
            if (thing_a > mid)
            {
                a.set(i, temp.get(thing_b));
                thing_b++;
            }
            else if (thing_b > last)
            {
                a.set(i, temp.get(thing_a));
                thing_a++;
            }
            else if (temp.get(thing_a).compareTo(temp.get(thing_b)) < 0)
            {
                a.set(i, temp.get(thing_a));
                thing_a++;
            }
            else
            {
                a.set(i, temp.get(thing_b));
                thing_b++;
            }
  
        }
    } 

  /**
   *  Recursive mergesort of an array of integers
   *
   * @param  a      reference to an array of integers to be sorted
   * @param  first  starting index of range of values to be sorted
   * @param  last   ending index of range of values to be sorted
   */
    public void mergeSort(ArrayList<Comparable> a, int first, int last)
    {
        if (last - first == 0) {}
        else if (last - first == 1) {
            if (a.get(first).compareTo(a.get(last)) > 0) {
                Comparable temp = a.get(first);
                a.set(first, a.get(last));
                a.set(last, temp);
            }
        }
        else
        {
            int mid = (first + last) / 2;
            mergeSort (a, first, mid);
            mergeSort (a, mid + 1, last);
            merge(a, first, mid, last);
        }
    }