Сортировка слиянием — это эффективный алгоритм сортировки, основанный на операциях слияния. Этот алгоритм является очень типичным примером применения подхода «разделяй и властвуй».

Сначала рассмотрим, как объединить две упорядоченные последовательности. Это очень просто: нужно сравнить первые числа двух последовательностей, сначала взять меньшее и после взятия удалить это число из соответствующей последовательности. Затем сравнить снова; если одна последовательность пуста, просто по одному извлечь данные из другой последовательности.

// Слить упорядоченные массивы a[] и b[] в c[] void MemeryArray(int a[], int n, int b[], int m, int c[]) { int i, j, k; i = j = k = 0; while (i < n && j < m) { if (a[i] < b[j]) c[k++] = a[i++]; else c[k++] = b[j++]; } while (i < n) c[k++] = a[i++]; while (j < m) c[k++] = b[j++]; }

Видно, что слияние упорядоченных последовательностей довольно эффективно и может достигать O(n).

После решения вышеописанной задачи слияния упорядоченных последовательностей рассмотрим сортировку слиянием. Её основная идея — разделить массив на две группы, A и B. Если данные внутри каждой группы упорядочены, то эти две группы данных можно удобно отсортировать. Как сделать данные внутри этих двух групп упорядоченными?

Вы можете далее разделить группы A и B на две группы каждую. И так далее. Когда разделённая подгруппа содержит только один элемент данных, подгруппу можно считать уже упорядоченной, а затем объединить две соседние подгруппы. Таким образом, сортировка слиянием завершается путём рекурсивного разложения последовательности сначала, а затем слияния последовательностей.

// Объединить две упорядоченные последовательности a[first...mid] и a[mid...last]. void mergearray(int a[], int first, int mid, int last, int temp[]) { int i = first, j = mid + 1; int m = mid, n = last; int k = 0; while (i <= m && j <= n) { if (a[i] <= a[j]) temp[k++] = a[i++]; else temp[k++] = a[j++]; } while (i <= m) temp[k++] = a[i++]; while (j <= n) temp[k++] = a[j++]; for (i = 0; i < k; i++) a[first + i] = temp[i]; } void mergesort(int a[], int first, int last, int temp[]) { if (first < last) { int mid = (first + last) / 2; mergesort(a, first, mid, temp); // Левая часть упорядочена mergesort(a, mid + 1, last, temp); // Правая часть упорядочена mergearray(a, first, mid, last, temp); // Затем слить две упорядоченные последовательности } } bool MergeSort(int a[], int n) { int *p = new int[n]; if (p == NULL) return false; mergesort(a, 0, n - 1, p); delete[] p; return true; }

Эффективность сортировки слиянием довольно высока. Пусть длина последовательности равна N. Всего требуется logN шагов, чтобы разделить последовательность на небольшие последовательности. Каждый шаг — это процесс слияния упорядоченных последовательностей, и временную сложность можно записать как O(N), поэтому в сумме получается O(N*logN). Поскольку сортировка слиянием каждый раз работает со смежными данными, среди нескольких методов сортировки со сложностью O(N*logN) (быстрая сортировка, сортировка слиянием, сортировка Шелла, пирамидальная сортировка) сортировка слиянием также является относительно эффективной.

На моем компьютере я сравнил пузырьковую сортировку, сортировку прямым включением, сортировку слиянием и прямое использование системной qsort() (все в Release-версии).

Тест с 20,000 случайными элементами данных:

Тест с 50,000 случайными элементами данных:

Затем протестируйте с 200,000 случайными элементами данных:

Примечание: В некоторых книгах в mergearray() выделяется временный массив при слиянии упорядоченных последовательностей, но слишком много операций new отнимает очень много времени. Поэтому было внесено небольшое изменение. Только один временный массив выделяется с помощью new в MergeSort(). Все последующие операции совместно используют этот временный массив.

Автор: MoreWindows

Оригинал: https://blog.csdn.net/morewindows/article/details/6678165