/**
* 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
*/
private void merge(ArrayList<Comparable> a, int first, int mid, int last) {
int x;
int i;
ArrayList<Comparable> left = new ArrayList<Comparable>();
ArrayList<Comparable> right = new ArrayList<Comparable>();
mergeSort(a,first,mid);
for(i = 0; i < a.size() - mid; i++){
left.add(i,a.get(i));
a.remove(i);
}
mergeSort(a,mid,last);
for (x = mid; x < a.size(); x++) {
right.add(x,a.get(x));
a.remove(x);
}
if ((left.get(i).compareTo(right.get(x))) > 0) {
i++;
a.add(i);
} else if (i < x) {
x++;
a.add(x);
}
System.out.println();
System.out.println("Merge");
System.out.println();
}
/**
* 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) {
int mid = (first + last)/2;
if(first == last){
}else if(last - first == 1){
merge(a,first, mid ,last);
}else{
last = mid;
}
}