def bubble_sort(arr: list) -> list:
    """バブルソート - 安定・in-place
 
    隣接要素を比較・交換し、最大値を末尾に移動させることを繰り返す。
    最適化: 1パスで交換がなければソート済みと判定して早期終了する。
 
    Args:
        arr: ソート対象のリスト（破壊的に変更される）
 
    Returns:
        ソート済みのリスト（入力と同一オブジェクト）
 
    計算量:
        最良: O(n)   -- 入力がソート済みの場合
        平均: O(n^2)
        最悪: O(n^2)
        空間: O(1)
    """
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr
 
 
# --- 動作確認 ---
if __name__ == "__main__":
    data = [64, 34, 25, 12, 22, 11, 90]
    print(f"入力: {data}")
    result = bubble_sort(data)
    print(f"出力: {result}")
    # 入力: [64, 34, 25, 12, 22, 11, 90]
    # 出力: [11, 12, 22, 25, 34, 64, 90]
 
    # ソート済みデータ → O(n) で完了
    sorted_data = [1, 2, 3, 4, 5]
    bubble_sort(sorted_data)
    print(f"ソート済み: {sorted_data}")  # [1, 2, 3, 4, 5]

def cocktail_shaker_sort(arr: list) -> list:
    """カクテルシェーカーソート（双方向バブルソート）
 
    バブルソートの改良版。前方向と後方向を交互にスキャンする。
    末尾付近の小さい値の移動が高速化される。
 
    計算量は最悪 O(n^2) で変わらないが、定数係数が改善される場合がある。
    """
    n = len(arr)
    start = 0
    end = n - 1
    swapped = True
 
    while swapped:
        swapped = False
 
        # 前方スキャン: 最大値を末尾へ
        for i in range(start, end):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        end -= 1
 
        if not swapped:
            break
 
        swapped = False
 
        # 後方スキャン: 最小値を先頭へ
        for i in range(end, start, -1):
            if arr[i] < arr[i - 1]:
                arr[i], arr[i - 1] = arr[i - 1], arr[i]
                swapped = True
        start += 1
 
    return arr
 
 
# --- 動作確認 ---
if __name__ == "__main__":
    data = [5, 1, 4, 2, 8, 0, 2]
    print(cocktail_shaker_sort(data))  # [0, 1, 2, 2, 4, 5, 8]

def selection_sort(arr: list) -> list:
    """選択ソート - 不安定・in-place
 
    未ソート部分の最小値を見つけ、先頭に配置することを繰り返す。
    交換回数は常に O(n) であり、書き込みコストが高い場合に有利。
 
    Args:
        arr: ソート対象のリスト
 
    Returns:
        ソート済みのリスト
 
    計算量:
        最良/平均/最悪: O(n^2) -- 入力に依らず常に同じ
        空間: O(1)
    """
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr
 
 
# --- 動作確認 ---
if __name__ == "__main__":
    data = [29, 10, 14, 37, 13]
    print(selection_sort(data))  # [10, 13, 14, 29, 37]

def insertion_sort(arr: list) -> list:
    """挿入ソート - 安定・in-place・適応的
 
    ソート済み部分に未ソート要素を一つずつ挿入する。
    ほぼ整列済みのデータに対して非常に高速（O(n) に近い）。
 
    Args:
        arr: ソート対象のリスト
 
    Returns:
        ソート済みのリスト
 
    計算量:
        最良: O(n)   -- 入力がソート済みの場合
        平均: O(n^2)
        最悪: O(n^2) -- 入力が逆順の場合
        空間: O(1)
    """
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr
 
 
# --- 動作確認 ---
if __name__ == "__main__":
    # ランダムデータ
    data = [5, 2, 4, 6, 1, 3]
    print(insertion_sort(data))  # [1, 2, 3, 4, 5, 6]
 
    # ほぼ整列済みデータ → O(n) に近い
    nearly_sorted = [1, 3, 2, 4, 6, 5]
    print(insertion_sort(nearly_sorted))  # [1, 2, 3, 4, 5, 6]

import bisect
 
def binary_insertion_sort(arr: list) -> list:
    """二分挿入ソート - 安定・in-place
 
    挿入位置を二分探索で決定する改良版。
    比較回数は O(n log n) に削減されるが、
    シフト操作は O(n^2) のまま。
 
    連結リストと組み合わせればシフトが O(1) になるが、
    二分探索には O(n) のアクセスが必要なため相殺される。
    """
    for i in range(1, len(arr)):
        key = arr[i]
        # bisect_left で挿入位置を二分探索
        pos = bisect.bisect_left(arr, key, 0, i)
        # pos から i-1 までの要素を右にシフト
        for j in range(i, pos, -1):
            arr[j] = arr[j - 1]
        arr[pos] = key
    return arr
 
 
# --- 動作確認 ---
if __name__ == "__main__":
    data = [37, 23, 0, 17, 12, 72, 31]
    print(binary_insertion_sort(data))  # [0, 12, 17, 23, 31, 37, 72]

def merge_sort(arr: list) -> list:
    """マージソート - 安定・O(n) 追加メモリ
 
    分割統治法により配列を再帰的に分割・マージする。
    安定性と O(n log n) の保証を兼ね備える。
 
    Args:
        arr: ソート対象のリスト
 
    Returns:
        新しいソート済みリスト
 
    計算量:
        最良/平均/最悪: O(n log n)
        空間: O(n) -- マージ時の一時配列
    """
    if len(arr) <= 1:
        return arr
 
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return _merge(left, right)
 
 
def _merge(left: list, right: list) -> list:
    """2つのソート済み配列をマージする
 
    両方の配列の先頭から比較し、小さい方を結果に追加する。
    <= で比較することで安定性を保証する。
    """
    result = []
    i = j = 0
    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
 
 
# --- 動作確認 ---
if __name__ == "__main__":
    data = [38, 27, 43, 3, 9, 82, 10]
    print(merge_sort(data))  # [3, 9, 10, 27, 38, 43, 82]

def merge_sort_bottom_up(arr: list) -> list:
    """ボトムアップ・マージソート（反復版）
 
    再帰を使わず、サイズ 1 の部分配列から始めて
    順次マージサイズを倍にしていく。
    再帰版と同じ O(n log n) だが、関数呼び出しの
    オーバーヘッドがない。
    """
    n = len(arr)
    if n <= 1:
        return arr[:]
 
    result = arr[:]
    width = 1
 
    while width < n:
        for i in range(0, n, 2 * width):
            left = result[i:i + width]
            right = result[i + width:i + 2 * width]
            merged = _merge(left, right)
            result[i:i + len(merged)] = merged
        width *= 2
 
    return result
 
 
# --- 動作確認 ---
if __name__ == "__main__":
    data = [5, 2, 4, 7, 1, 3, 2, 6]
    print(merge_sort_bottom_up(data))  # [1, 2, 2, 3, 4, 5, 6, 7]

def quick_sort(arr: list, low: int = 0, high: int = None) -> list:
    """クイックソート - 不安定・in-place
 
    ピボットによる分割と再帰的ソートを行う。
    平均的に最も高速な汎用ソートアルゴリズム。
 
    Args:
        arr: ソート対象のリスト
        low: ソート範囲の開始インデックス
        high: ソート範囲の終了インデックス
 
    Returns:
        ソート済みのリスト
 
    計算量:
        最良: O(n log n)
        平均: O(n log n)
        最悪: O(n^2) -- ソート済み配列 + 末尾ピボット
        空間: O(log n) -- 再帰スタック（平均）
    """
    if high is None:
        high = len(arr) - 1
    if low < high:
        pivot_idx = _partition(arr, low, high)
        quick_sort(arr, low, pivot_idx - 1)
        quick_sort(arr, pivot_idx + 1, high)
    return arr
 
 
def _partition(arr: list, low: int, high: int) -> int:
    """Lomuto のパーティション"""
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1
 
 
# --- 動作確認 ---
if __name__ == "__main__":
    data = [10, 7, 8, 9, 1, 5]
    print(quick_sort(data[:]))  # [1, 5, 7, 8, 9, 10]

import random
 
 
def quick_sort_randomized(arr: list, low: int = 0, high: int = None) -> list:
    """ランダム化クイックソート
 
    ピボットをランダムに選択することで、
    特定の入力パターンによる最悪ケースを確率的に回避する。
    期待計算量は O(n log n)。
    """
    if high is None:
        high = len(arr) - 1
    if low < high:
        rand_idx = random.randint(low, high)
        arr[rand_idx], arr[high] = arr[high], arr[rand_idx]
        pivot_idx = _partition(arr, low, high)
        quick_sort_randomized(arr, low, pivot_idx - 1)
        quick_sort_randomized(arr, pivot_idx + 1, high)
    return arr
 
 
def partition_median_of_three(arr: list, low: int, high: int) -> int:
    """三値の中央値によるパーティション
 
    先頭・中央・末尾の3要素の中央値をピボットに選ぶ。
    ソート済み・逆順データでの最悪ケースを回避する。
    """
    mid = (low + high) // 2
    if arr[low] > arr[mid]:
        arr[low], arr[mid] = arr[mid], arr[low]
    if arr[low] > arr[high]:
        arr[low], arr[high] = arr[high], arr[low]
    if arr[mid] > arr[high]:
        arr[mid], arr[high] = arr[high], arr[mid]
    # 中央値(mid)をピボットとして high-1 に退避
    arr[mid], arr[high - 1] = arr[high - 1], arr[mid]
    pivot = arr[high - 1]
 
    i = low
    j = high - 1
    while True:
        i += 1
        while arr[i] < pivot:
            i += 1
        j -= 1
        while arr[j] > pivot:
            j -= 1
        if i >= j:
            break
        arr[i], arr[j] = arr[j], arr[i]
    arr[i], arr[high - 1] = arr[high - 1], arr[i]
    return i
 
 
# --- 動作確認 ---
if __name__ == "__main__":
    data = [10, 7, 8, 9, 1, 5]
    print(quick_sort_randomized(data[:]))  # [1, 5, 7, 8, 9, 10]

def quick_sort_three_way(arr: list, low: int = 0, high: int = None) -> list:
    """三方分割クイックソート
 
    配列を「ピボット未満」「ピボットと等しい」「ピボット超過」
    の3つに分割する。重複要素が多い場合に特に有効。
 
    計算量:
        重複なし: O(n log n)
        重複多数: O(n) に近づく（等しい要素をスキップ）
    """
    if high is None:
        high = len(arr) - 1
    if low >= high:
        return arr
 
    pivot = arr[low]
    lt = low      # arr[low..lt-1]   < pivot
    i = low + 1   # arr[lt..i-1]    == pivot
    gt = high     # arr[gt+1..high]  > pivot
 
    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1
        else:
            i += 1
 
    quick_sort_three_way(arr, low, lt - 1)
    quick_sort_three_way(arr, gt + 1, high)
    return arr
 
 
# --- 動作確認 ---
if __name__ == "__main__":
    data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
    print(quick_sort_three_way(data))  # [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

def heap_sort(arr: list) -> list:
    """ヒープソート - 不安定・in-place・O(n log n) 保証
 
    最大ヒープを構築し、ルートを末尾に移動させることを繰り返す。
    最悪でも O(n log n) が保証され、O(1) 追加メモリで動作する。
 
    Args:
        arr: ソート対象のリスト
 
    Returns:
        ソート済みのリスト
 
    計算量:
        最良/平均/最悪: O(n log n)
        空間: O(1)
    """
    n = len(arr)
 
    # 最大ヒープ構築（ボトムアップ）
    for i in range(n // 2 - 1, -1, -1):
        _heapify(arr, n, i)
 
    # ルートを末尾に移動してヒープサイズを縮小
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        _heapify(arr, i, 0)
 
    return arr
 
 
def _heapify(arr: list, n: int, i: int) -> None:
    """ノード i を根とする部分木を最大ヒープ化する"""
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
 
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
 
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        _heapify(arr, n, largest)
 
 
# --- 動作確認 ---
if __name__ == "__main__":
    data = [12, 11, 13, 5, 6, 7]
    print(heap_sort(data))  # [5, 6, 7, 11, 12, 13]
 
    data2 = [4, 10, 3, 5, 1]
    print(heap_sort(data2))  # [1, 3, 4, 5, 10]

def counting_sort(arr: list) -> list:
    """計数ソート - 安定・O(n + k)
 
    要素の出現回数をカウントし、累積和で位置を決定する。
    整数データで値の範囲 k が小さい場合に最適。
 
    Args:
        arr: 整数のリスト
 
    Returns:
        新しいソート済みリスト
 
    計算量:
        時間: O(n + k) -- k は値の範囲
        空間: O(n + k)
    """
    if not arr:
        return arr
 
    max_val = max(arr)
    min_val = min(arr)
    range_val = max_val - min_val + 1
 
    count = [0] * range_val
    output = [0] * len(arr)
 
    for num in arr:
        count[num - min_val] += 1
 
    for i in range(1, range_val):
        count[i] += count[i - 1]
 
    for i in range(len(arr) - 1, -1, -1):
        output[count[arr[i] - min_val] - 1] = arr[i]
        count[arr[i] - min_val] -= 1
 
    return output
 
 
# --- 動作確認 ---
if __name__ == "__main__":
    data = [4, 2, 2, 8, 3, 3, 1]
    print(counting_sort(data))  # [1, 2, 2, 3, 3, 4, 8]

def radix_sort(arr: list) -> list:
    """基数ソート (LSD) - 安定・O(d * (n + k))
 
    最下位桁から順に計数ソートを適用する。
    d は最大桁数、k は基数（通常 10）。
 
    Args:
        arr: 非負整数のリスト
 
    Returns:
        新しいソート済みリスト
 
    計算量:
        時間: O(d * (n + k))
        空間: O(n + k)
    """
    if not arr:
        return arr
 
    result = arr[:]
    max_val = max(result)
 
    exp = 1
    while max_val // exp > 0:
        result = _counting_sort_by_digit(result, exp)
        exp *= 10
 
    return result
 
 
def _counting_sort_by_digit(arr: list, exp: int) -> list:
    """特定の桁に基づく計数ソート"""
    n = len(arr)
    output = [0] * n
    count = [0] * 10
 
    for num in arr:
        digit = (num // exp) % 10
        count[digit] += 1
 
    for i in range(1, 10):
        count[i] += count[i - 1]
 
    for i in range(n - 1, -1, -1):
        digit = (arr[i] // exp) % 10
        output[count[digit] - 1] = arr[i]
        count[digit] -= 1
 
    return output
 
 
# --- 動作確認 ---
if __name__ == "__main__":
    data = [170, 45, 75, 90, 802, 24, 2, 66]
    print(radix_sort(data))  # [2, 24, 45, 66, 75, 90, 170, 802]

def bucket_sort(arr: list, bucket_count: int = 10) -> list:
    """バケットソート - 安定（内部ソートが安定なら）
 
    値の範囲を等間隔のバケットに分割し、
    各バケット内を挿入ソートでソートする。
    一様分布の浮動小数点データに最適。
 
    Args:
        arr: 数値のリスト
        bucket_count: バケットの数
 
    Returns:
        新しいソート済みリスト
 
    計算量:
        平均: O(n + n^2/k + k) -- k=n なら O(n)
        最悪: O(n^2) -- 全要素が同一バケットに集中
        空間: O(n + k)
    """
    if not arr:
        return arr
 
    min_val = min(arr)
    max_val = max(arr)
 
    if min_val == max_val:
        return arr[:]
 
    range_val = max_val - min_val
 
    buckets: list[list] = [[] for _ in range(bucket_count)]
 
    for num in arr:
        idx = int((num - min_val) / range_val * (bucket_count - 1))
        buckets[idx].append(num)
 
    result = []
    for bucket in buckets:
        insertion_sort(bucket)
        result.extend(bucket)
 
    return result
 
 
# --- 動作確認 ---
if __name__ == "__main__":
    data = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
    print(bucket_sort(data, 5))
    # [0.1234, 0.3434, 0.565, 0.656, 0.665, 0.897]

def shell_sort(arr: list) -> list:
    """シェルソート - 不安定・in-place
 
    ギャップを縮小しながら挿入ソートを繰り返す。
    ギャップ列の選択により計算量が変わる。
 
    Knuth のギャップ列: 1, 4, 13, 40, 121, ...  (3h + 1)
    このギャップ列での計算量は O(n^{3/2})。
 
    Args:
        arr: ソート対象のリスト
 
    Returns:
        ソート済みのリスト
 
    計算量:
        Knuth列: O(n^{3/2})
        Sedgewick列: O(n^{4/3})
        空間: O(1)
    """
    n = len(arr)
 
    # Knuth のギャップ列を計算
    gap = 1
    while gap < n // 3:
        gap = gap * 3 + 1  # 1, 4, 13, 40, 121, ...
 
    while gap >= 1:
        # ギャップ付き挿入ソート
        for i in range(gap, n):
            key = arr[i]
            j = i
            while j >= gap and arr[j - gap] > key:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = key
        gap //= 3
 
    return arr
 
 
# --- 動作確認 ---
if __name__ == "__main__":
    data = [35, 33, 42, 10, 14, 19, 27, 44, 26, 31]
    print(shell_sort(data))  # [10, 14, 19, 26, 27, 31, 33, 35, 42, 44]

import math
 
 
def introsort(arr: list) -> list:
    """Introsort（内省的ソート）
 
    クイックソート + ヒープソート + 挿入ソートのハイブリッド。
    C++ の std::sort の基盤アルゴリズム。
 
    計算量:
        最良/平均/最悪: O(n log n)
        空間: O(log n)
    """
    max_depth = 2 * math.floor(math.log2(max(len(arr), 1)))
    _introsort_impl(arr, 0, len(arr) - 1, max_depth)
    return arr
 
 
def _introsort_impl(arr: list, low: int, high: int, depth_limit: int) -> None:
    """Introsort の内部実装"""
    INSERTION_THRESHOLD = 16
 
    while high - low + 1 > INSERTION_THRESHOLD:
        if depth_limit == 0:
            # 深度超過 → ヒープソートに切り替え
            sub = arr[low:high + 1]
            heap_sort(sub)
            arr[low:high + 1] = sub
            return
 
        depth_limit -= 1
 
        # 三値中央値でピボット選択
        mid = (low + high) // 2
        if arr[mid] < arr[low]:
            arr[low], arr[mid] = arr[mid], arr[low]
        if arr[high] < arr[low]:
            arr[low], arr[high] = arr[high], arr[low]
        if arr[high] < arr[mid]:
            arr[mid], arr[high] = arr[high], arr[mid]
 
        pivot = arr[mid]
        arr[mid], arr[high - 1] = arr[high - 1], arr[mid]
 
        # パーティション
        i = low
        j = high - 1
        while True:
            i += 1
            while arr[i] < pivot:
                i += 1
            j -= 1
            while arr[j] > pivot:
                j -= 1
            if i >= j:
                break
            arr[i], arr[j] = arr[j], arr[i]
 
        arr[i], arr[high - 1] = arr[high - 1], arr[i]
 
        # 短い方を再帰、長い方をループ（末尾再帰最適化）
        if i - low < high - i:
            _introsort_impl(arr, low, i - 1, depth_limit)
            low = i + 1
        else:
            _introsort_impl(arr, i + 1, high, depth_limit)
            high = i - 1
 
    # 閾値以下は挿入ソート
    for i in range(low + 1, high + 1):
        key = arr[i]
        j = i - 1
        while j >= low and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
 
 
# --- 動作確認 ---
if __name__ == "__main__":
    data = [5, 3, 8, 4, 2, 7, 1, 10, 6, 9]
    print(introsort(data))  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

# BAD: 常に末尾をピボットにする
# ソート済み配列で O(n^2) に退化する
def bad_quicksort(arr, low, high):
    pivot = arr[high]  # ソート済みで最悪ケース
    # ...パーティション処理...
 
 
# GOOD: 三値の中央値 or ランダム選択
import random
 
def good_quicksort(arr, low, high):
    if low < high:
        # ランダムピボット選択
        rand_idx = random.randint(low, high)
        arr[rand_idx], arr[high] = arr[high], arr[rand_idx]
        # ...パーティション処理...

# BAD: 値域が巨大な場合に計数ソートを使う
data = [1, 1000000000, 2]  # count 配列が 10^9 サイズ!
counting_sort(data)         # メモリ不足でクラッシュ
 
# GOOD: 値域を確認してからアルゴリズムを選択
def smart_sort(data: list) -> list:
    if not data:
        return data
    range_val = max(data) - min(data) + 1
    if range_val <= len(data) * 10:
        return counting_sort(data)  # 値域が小さい → 計数ソート
    else:
        return sorted(data)  # 値域が大きい → 比較ソート

# BAD: レコードのソートに不安定ソートを使い順序が崩れる
students = [(3, "Alice"), (1, "Bob"), (3, "Charlie")]
# ヒープソートを使うと同一キーの Alice, Charlie の順序が保証されない
 
# GOOD: 安定ソートを使う（Python の sort は TimSort で安定）
students.sort(key=lambda x: x[0])
# [(1, "Bob"), (3, "Alice"), (3, "Charlie")]  ← 元の順序が保持される

# BAD: 再帰深度を制限しないクイックソート
# 最悪ケースで再帰深度が O(n) になり、スタックオーバーフローが発生
def bad_quicksort(arr, low, high):
    if low < high:
        p = partition(arr, low, high)
        bad_quicksort(arr, low, p - 1)   # 左側を再帰
        bad_quicksort(arr, p + 1, high)  # 右側を再帰
        # n=10000 のソート済みデータで RecursionError!
 
# GOOD: Introsort パターンで深度制限 + 末尾再帰最適化
import math
 
def good_quicksort(arr, low, high, depth=None):
    if depth is None:
        depth = 2 * math.floor(math.log2(max(len(arr), 1)))
    while low < high:
        if depth == 0:
            # ヒープソートにフォールバック
            sub = arr[low:high + 1]
            heap_sort(sub)
            arr[low:high + 1] = sub
            return
        depth -= 1
        p = _partition(arr, low, high)
        # 短い方を再帰、長い方をループ（末尾再帰最適化）
        if p - low < high - p:
            good_quicksort(arr, low, p - 1, depth)
            low = p + 1
        else:
            good_quicksort(arr, p + 1, high, depth)
            high = p - 1