mergeSort.java

void merge(int[] arr, int start, int mid, int end, int[] tmp) {
	int i = 0;
	int j = 0;
	int k = 0;
	while (i <= mid && j <= end) {
		if (arr[i] < arr[j]) {
			tmp[k++] = arr[i++];
		} else {
			tmp[k++] = arr[j++];
		}
	}

	while (i <= mid) {
		tmp[k++] = arr[i++];
	}

	while (j <= end) {
		tmp[k++] = arr[j++];
	}

	for (int idx = 0; idx <= k; idx ++) {
		arr[start + idx] = tmp[idx];
	}
}

void mergeSort(int[] arr, int start, int end, int[] tmp) {
	if (start < end) {
		int mid = (start + end) / 2;
		mergeSort(arr, start, mid, tmp);
		mergeSort(arr, mid + 1, end, tmp);
		merge(arr, start, mid, end, tmp);
	}
}

mergeSort(arr, 0, n - 1, new int[n]);