/**
* 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);
}
}