マージソート

8.1 マージソートの定義

マージソート (Merge Sort) は、効率的で安定した比較ベースの ソートアルゴリズムで、「分割して統治する」アプローチを使用して要素を 整列します。アルゴリズムは配列を2つに分割し、それぞれの半分を再帰的に ソートし、その後ソートされた半分を一つのソートされた配列に統合します。

動作原理:

分割:

• 入力配列を半分に分けて、2つの部分配列を得る。
• 各部分配列を1要素の配列（または空の配列）になるまで再帰的に分割します。

統合:

• 隣接する2つの部分配列を1つのソートされた配列に統合します。
• 1つのソートされた配列が得られるまでこのプロセスを繰り返します。

マージソートの時間と空間の計算量

時間計算量:

• 最悪のケース: O(n log n)
• 平均的なケース: O(n log n)
• 最良のケース: O(n log n)

空間計算量:

O(n) — 一時的な部分配列を保存するのに追加のメモリが必要です。

8.2 トップダウンマージメソッド

元のシーケンスを再帰的に半分に分割し、1要素ごとのサブシーケンスになるまで 続けます。得られたサブシーケンスからマージメソッドを使って整列されたペアを 形成し、その後に整列された四つ組を形成します。

シーケンスを見てみましょう:

シーケンスを2つに分割します（再帰的に、ペアになるまで）。

各サブシーケンスをマージメソッドで整列し、完成したシーケンスを得る。

8.3 マージソートアルゴリズムの実装

ここで再帰が役立ちます！これは以前のものに比べて非常に良くて速い アルゴリズムです。配列を半分に分け、それぞれを別々にソートし、その後 ソートされた部分を素早く統合します。

実装はこんな感じです:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # 配列の中央を見つける
        left_half = arr[:mid]  # 配列を2つの部分配列に分割
        right_half = arr[mid:]
        
        merge_sort(left_half)  # 左半分を再帰的にソート
        merge_sort(right_half)  # 右半分を再帰的にソート
        
        i = j = k = 0
        
        # ソートされた半分の統合
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1
        
        # 残りの要素のチェック
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1
        
        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
    return arr

# 使用例:
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("ソートされた配列:", sorted_arr)
# 出力: ソートされた配列: [3, 9, 10, 27, 38, 43, 82]

最初に重要なポイントがあります:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # 配列の中央を見つける
        left_half = arr[:mid]  # 配列を2つの部分配列に分割
        right_half = arr[mid:]
        
        merge_sort(left_half)  # 左半分を再帰的にソート
        merge_sort(right_half)  # 右半分を再帰的にソート

ここで何が起こっているか説明します:

1. 配列の中央を見つける
2. 配列を2つの部分に分割
3. 各部分を別々にソート

この方法によりアルゴリズムが大幅に速くなります。