【解説】　マージソート(Merge Sort)

特徴と性能

マージソートは「安定感」が抜群です。

• 時間計算量: O(n \log n)

  • 最悪の場合でも O(n \log n) です。クイックソートのように極端に遅くなることがありません。

• 空間計算量: " data-index-in-node="7">O

  • 合流の際に一時的に別の配列を用意するため、元の配列と同じ分のメモリを消費します。

• 安定性: 安定なソート

  • 合流時に左側の要素を優先することで、同じ値の順序を崩さずに済みます。

# マージソート
def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    # 1. 分割
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    # 2. 統合（マージ）して返す
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    # 左右のリストを比較して、小さい方をresultに追加
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # 残った要素（あれば）を最後に追加
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# 使用例
data = [38, 27, 43, 3, 9, 82, 10]
print(f"ソート後: {merge_sort(data)}")