Почему так долго работает сортировка слиянием?

Question

[BitNeBolt]

Почему массив из 30 чисел сортируется около полутора секунд? В чем ошибка реализации?

public static void mergeSort(int[] a) {
		int[] temp = new int[a.length];
		mergeSort(a, temp, 0, a.length-1);
	}

	private static void mergeSort(int[] a, int[] temp, int lo, int hi) {
		if (lo >= hi) return;

		/*if ((hi - lo) < 32) {
			insertionSort(a, lo, hi);
			return;
		}*/

		int mid = (lo + hi) / 2;

		mergeSort(a, temp, 0, mid);
		mergeSort(a, temp, mid+1, hi);

		merge(a, temp, lo, hi);
	}

	private static void merge(int[] a, int[] temp, int lo, int hi) {
		int mid = (lo + hi) / 2;

		int left = 0;
		int right = mid + 1;

		for (int i = 0; i < a.length; i++) temp[i] = a[i];

		for (int i = 0; i < a.length; i++) {
			if (left <= mid && right < a.length) {
				if (temp[left] < temp[right]) {
					a[i] = temp[left++];
				} else {
					a[i] = temp[right++];
				}
			} else if (left <= mid) {
				a[i] = temp[left++];
			} else if (right < a.length) {
				a[i] = temp[right++];
			}
		}
	}

Comments

[BitNeBolt]

Держу в курсе, здесь ещё ошибки при копировании в temp и обратно.

Answer 1

[Wataru]

mergeSort(a, temp, 0, mid);

Надо сортировать часть с lo по mid. А не с 0.