public class MergeSort {
	// mergeSort(): sorts the elements of a 
	public static void mergeSort(char[] a) {
		mergeSort(a, 0, a.length - 1);
	}

	private static void mergeSort(char[] a, int left, int right) {
		if (left < right) {
			// there are multiple elements to sort.

			// first, recursively sort the left and right sublists
			int mid = (left + right) / 2;
			mergeSort(a, left, mid);
			mergeSort(a, mid+1, right);

			// next, merge the sorted sublists into array temp
			char[] temp = new char[right - left + 1];

			int j = left;      // index of left sublist smallest element
			int k = mid + 1;   // index of right sublist smallest element

			for (int i = 0; i < temp.length; ++i) {
				// store the next smallest element into temp
				if ((j <= mid) && (k <= right)) {
					// need to grab the smaller of a[j] and a[k]
					if (a[j] <= a[k]) { // left has the smaller element
						temp[i] = a[j];
						++j;
					}
					else { // right has the smaller element
						temp[i] = a[k];
						++k;
					}
				}
				else if (j <= mid) { // can only grab from left half
					temp[i] = a[j];
					++j;
				}
				else { // can only grab from right half
					temp[i] = a[k];
					++k;
				}
			}

			// lastly, copy temp into a
			for (int i = 0; i < temp.length; ++i) {
				a[left + i] = temp[i];
			}
		}
	}
}