マージソート
アルゴリズムの仕組み
マージソートは、以下のステップで配列をソートします。
分割 (Divide): 配列を2つのほぼ等しいサイズのサブ配列に分割します。
征服 (Conquer): 分割したサブ配列を再帰的にマージソートでソートします。
統合 (Combine): ソートされた2つのサブ配列をマージして、1つのソートされた配列にします。
図による説明
配列 `` をマージソートでソートする過程を図で示します。
graph LR A[Unsorted Array: 5, 2, 8, 1, 9, 4, 7, 6] --> B(Divide) B --> C B --> D C --> E(Divide) D --> F(Divide) E --> G E --> H F --> I F --> J G --> K(Divide) H --> L(Divide) I --> M(Divide) J --> N(Divide) K --> O K --> P L --> Q L --> R M --> S M --> T N --> U N --> V O --> W(Merge) P --> W Q --> X(Merge) R --> X S --> Y(Merge) T --> Y U --> Z(Merge) V --> Z W --> AA X --> BB Y --> CC Z --> DD AA --> EE(Merge) BB --> EE CC --> FF(Merge) DD --> FF EE --> GG FF --> HH GG --> II(Merge) HH --> II II --> JJ[Sorted Array: 1, 2, 4, 5, 6, 7, 8, 9]
表による時間計算量の比較
ケース | 時間計算量 |
|---|---|
最良の場合 | O(n log n) |
平均的な場合 | O(n log n) |
最悪の場合 | O(n log n) |
特徴
安定なソート (同じ値の要素の順序が保持されます) [1]。
予測可能なパフォーマンス: 常にO(n log n)の時間計算量 [6].
並列処理に適している: 分割統治法のため、サブ配列のソートを並行して行うことができます。
追加のメモリが必要: マージ操作のために、元の配列と同じサイズの追加のメモリが必要です。
ソース内の関連情報
マージソートは、要素を選択して2つの部分列に分割するクイックソートとは対照的に、ソートされた2つの部分列をマージして1つのソートされたデータ列を作成します [4]。
要素数 n の配列に対するマージソートの時間計算量は O(n log n) です [2].
ソースには、再帰的なマージソート関数を完成させる問題があります [8]。
merge(A, 1, m, r)は2つのソートされたデータ配列をマージして1つのソートされた配列を作成する関数であり、これはすでに完成しているものとします [8]。