merge_sort

ソースコード

from titan_pylib.algorithm.sort.merge_sort import merge_sort

view on github

展開済みコード

 1# from titan_pylib.algorithm.sort.merge_sort import merge_sort
 2# from titan_pylib.my_class.supports_less_than import SupportsLessThan
 3from typing import Protocol
 4
 5
 6class SupportsLessThan(Protocol):
 7
 8    def __lt__(self, other) -> bool: ...
 9from typing import Iterable, TypeVar, Callable
10
11T = TypeVar("T", bound=SupportsLessThan)
12
13
14def merge_sort(
15    a: Iterable[T], key: Callable[[T, T], bool] = lambda s, t: s < t
16) -> list[T]:
17    """マージソートです。安定なはずです。
18    最悪 :math:`O(n\\log{n})` 時間です。
19
20    Args:
21        a (Iterable[T]): ソートする列です。
22        key (Callable[[T, T], bool], optional): 比較関数 `key` にしたがって比較演算をします。
23                                                (第1引数)<=(第2引数) のとき、 ``True`` を返すようにしてください。
24    """
25
26    def _sort(l: int, r: int) -> None:
27        if r - l <= 1:
28            return
29        if r - l == 2:
30            if not key(a[l], a[l + 1]):
31                a[l], a[l + 1] = a[l + 1], a[l]
32            return
33        mid = (l + r) // 2
34        _sort(l, mid)
35        _sort(mid, r)
36        i, j = l, mid
37        indx = 0
38        while i < mid and j < r:
39            if key(a[i], a[j]):
40                buff[indx] = a[i]
41                i += 1
42            else:
43                buff[indx] = a[j]
44                j += 1
45            indx += 1
46        for k in range(i, mid):
47            a[l + indx + k - i] = a[k]
48        for k in range(l, l + indx):
49            a[k] = buff[k - l]
50
51    a = list(a)
52    buff = [0] * len(a)
53    _sort(0, len(a))
54    return a

仕様

merge_sort(a: ~typing.Iterable[~titan_pylib.algorithm.sort.merge_sort.T], key: ~typing.Callable[[~titan_pylib.algorithm.sort.merge_sort.T, ~titan_pylib.algorithm.sort.merge_sort.T], bool] = <function <lambda>>) → list[T][source]

マージソートです。安定なはずです。 最悪 \(O(n\log{n})\) 時間です。

Parameters:

  • a (Iterable[T]) – ソートする列です。

  • key (Callable[[T, T], bool], optional) – 比較関数 key にしたがって比較演算をします。 (第1引数)<=(第2引数) のとき、 True を返すようにしてください。