BitNeBolt
@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++];
			}
		}
	}
  • Вопрос задан
  • 87 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.

mergeSort(a, temp, 0, mid);


Надо сортировать часть с lo по mid. А не с 0.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы