マージソートは、マージ操作に基づく効率的なソートアルゴリズムです。このアルゴリズムは、分割統治法（Divide and Conquer）を採用した非常に典型的な例です。

まず、2つの整列済みの数列をどのようにマージするかを考えます。これは非常に簡単で、2つの数列の最初の数を比較し、小さい方を先に取り出し、取り出したら対応する数列からその数を削除します。その後、再び比較を行います。もしどちらかの数列が空になったら、もう一方の数列のデータを順に取り出すだけです。

//整列済みの配列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の2つのグループに分け、この2つのグループ内のデータがそれぞれ整列済みであれば、その2つのグループのデータを簡単にソートできるというものです。では、どうやってこの2つのグループ内のデータを整列させるのでしょうか？

A、Bグループをそれぞれさらに2つのグループに分けることができます。同様に繰り返し、分割された小グループが1つのデータだけになったとき、その小グループ内はすでに整列済みと見なせます。その後、隣接する2つの小グループをマージすればよいのです。このように、まず数列を再帰的に分割し、次に数列をマージすることでマージソートが完成します。

//整列済みの2つの数列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); //次に2つの整列済みの数列をマージする } } 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 バージョンです）。

20000 個のランダムデータに対してテスト：

50000 個のランダムデータに対してテスト：

さらに 200000 個のランダムデータに対してテスト：

注：一部の書籍では、mergearray() で整列済みの数列をマージする際に一時配列を割り当てますが、new 操作が多すぎると非常に時間がかかります。そのため、少し変更を加えました。MergeSort() 内で一時配列を1つだけ new し、以降の操作はすべてこの1つの一時配列を共用します。

作者：MoreWindows

原文：https://blog.csdn.net/morewindows/article/details/6678165