Pythonのソートメソッド「sort」の正体はなんじゃらほい！？

## はじめに

　久々にQiitaの記事を書きます。*nishiwakki*です。今回は「*Pythonその2 Advent Calendar 2020*」の「12日目」枠として本記事を投稿します！（投稿、日付変更直前で申し訳ないです...　急いでいたので図の色が全体的に気持ち悪いです）

　趣味でPythonを使って、ちょっとした遊び開発だったり、競プロをしたりするのですが、その際に**ソート**をよく利用します。ソートというと、バブルソートやクイックソートなどが頭をよぎりますが、Pythonのソートメソッド`sort`で使用されるのは一体何ソートなのかな〜？　とふと思ったのがきっかけです。

```python
# ソートメソッド sort を実際に使ってみる
l = [5, 1, 3, 4, 2]
print(l) # 出力結果: [5, 1, 3, 4, 2]
l.sort()
print(l) # 出力結果: [1, 2, 3, 4, 5]
```

　「ソートなんて興味ないw」な方や「男は黙ってボゴソートでしょ」という方々も、是非読んでいただけると嬉しいです！


## 結論からいうと

　Pythonで用いられているソートアルゴリズムは、「**Timsort**」と呼ばれるものだそうです。
（Python公式ドキュメント「[Sorting HOW TO](https://docs.python.org/3/howto/sorting.html)」より）

　......は？知らんと思ったそこのアナタ、安心してください。私も知りませんでした...（泣）


## Timsortのプロフィール

　Timちゃんの上から下まで隅々と調査しました。

|項目|オーダー|説明|
|:---|:---|:---|
|平均計算時間|$O(n \log n)$|ソートにかかる平均的な時間|
|最良計算時間|$O(n)$|元の並びが良く最速でソートできた場合の時間|
|**最悪計算時間**|$O(n \log n)$|元の並びが悪くソートに最も長くかかった場合の時間|
|メモリ使用量|$O(n)$|空間計算量とも。ソートに使用するメモリの量|
|**安定性**|あり|同値のデータの順番がソート前・後で変わらない|

　ソートの計算量は、最悪計算時間がピックアップされることが多いです。オーダー記法で書いてあるので、難しいと感じる方もいらっしゃると思いますが、他のソートと比較してみるとこんな感じです。

|ソート|最悪計算時間|
|:---|:---|
|バブルソート|$O(n^2)$|
|クイックソート|$O(n^2)$|
|**Timsort**|$O(n \log n)$|

　そして、オーダー記法はこのような速い・遅い関係になっています。

【速】$O(1)$ < $O(\log n)$ < $O(n)$ < $O(n \log n)$ < $O(n^2)$【遅】

　Timちゃんは高速なソートアルゴリズムだということですね、優秀！
　安定性があるのも嬉しいです！

## Timsortの正体

　Timちゃんが優秀なのはわかりましたが、一体何者なのでしょうか？
　結論からいうと、Timsortは下記2つの有名ソートの**ハイブリッド**（いいとこ取り）です。

- [挿入ソート](https://ja.wikipedia.org/wiki/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88)
    - 【メリット】ソート前にある程度整列済みだと速い（最良計算時間が速い）
- [マージソート](https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88)
    - 【メリット】安定したソート速度が見込める

　2つのソートの詳細については、本記事では省略します。
　本記事では、シンプル実装のTimsortを見ていきます！（実際のPythonの`sort`の実装は複雑です）

---

　Timsortは大きく分けて4つのステップがあります！

1. **minRunの計算**
2. **minRunをもとに配列を分割**
3. **分割した配列ごとに挿入ソートを実施**
4. **分割したソート済み配列にマージソートを実施**

> 【注意】
> Timsortを行いたい配列の要素数 $N$ が $N < 64$ の場合、
> ステップ2の配列分割は実施されず、入力配列に挿入ソートのみが実施されて終了します。

　ステップごとに見ていきます。

### STEP1. minRunの計算

　ソートを行う入力配列を、サブ配列と呼ばれる配列に分割します。
　そのサブ配列の最低要素数を`minRun`と呼び、これを計算します。

![1.001.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/298123/4d9da166-af87-29a0-bea9-3bd48e4eb26d.jpeg)

　`minRun`の値には、次の3条件があります。

- **入力配列の要素数`N`と`minRun`について、 $\frac{N}{minRun}$ が2の累乗（2, 4, 8, 16,...）か、それに近い値であること**
- **`minRun`の値は大きすぎないこと（ $minRun < 256$ ）**
- **`minRun`の値は小さすぎないこと（ $minRun > 8$ ）**

　上記条件を満たし、最も高いパフォーマンスを出せるのは $32 \leqq minRun \leqq 64$ とのことです。
　この数値を入力配列の要素数`N`から計算するために次のような関数を使用します。

```python
# minRunの計算をする関数
def calcMinRun(n):
    r = 0
    while n >= 64:
        # 最下位ビットが1である場合、r=1になる
        r |= n & 1
        # nを1桁右シフト(n // 2 みたいなもの)
        n >>= 1
    return n + r
```

　ぱっと見て難しいですが、要は、`N`を2進数で表した時の上位6ビット( $2^6 = 64$ )を除いた、下位ビットに`1`が一つでもある場合に、`r`の値が`1`になります。（`r`は `0` or `1` です）

![2.002.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/298123/194b447a-36fd-91f5-607b-c7c36cc5b8c0.jpeg)

　上の例1, 2はそれぞれ `minRun = 38`, `minRun = 32` となります。

### STEP2. minRunをもとに配列を分割

　入力配列1を`minRun`の要素数ずつにスライスし、サブ配列とします。
　STEP1の例1だと、次のようになります。

![名称未設定.001.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/298123/7c1164fb-5270-d9d4-8a7e-d29378ee5875.jpeg)

　最後のサブ配列が`minRun`よりも小さくなることがありますが、（本記事では）そのままで扱います。
　（後述の「実際のTimsortはもっとすごい」にて少し説明を加えます。）

　なお、 $\frac{N}{minRun} = 31.921...$ となっており、 $2^5 = 32$ に近い値であることがわかります。

### 3. 分割した配列ごとに挿入ソートを実施

　分割したサブ配列全てに対して**挿入ソート**を行います。本記事では、普通の挿入ソートのプログラムを使用します。

<details><summary>挿入ソートの関数</summary><div>

```python
# 挿入ソートを実施する関数
def insertionSort(arr, l, r):
    for i in range(l+1, r+1):
        j = i
        while j > l and arr[j] < arr[j-1]:
            arr[j], arr[j-1] = arr[j-1], arr[j]
            j -= 1
```

</div></details>

　それでは、ここまでのステップの内容を実際にプログラムで見てみましょう！

```python
# Timsortを実施する関数
def timSort(arr):
    # リストの長さを取得
    n = len(arr)
    # 【STEP1】長さをもとにminRunを計算
    minRun = calcMinRun(n)
    # 【STEP2】サブ配列に分割(minRunの長さごとに繰り返し実行)
    for start in range(0, n, minRun):
        # 最終サブ配列時にリストの範囲外アクセスを防ぐ
        end = min(start + minRun - 1, n - 1)
        # 【STEP3】サブ配列内で挿入ソート実施
        insertionSort(arr, start, end)
    :
    # 【STEP4】分割したソート済み配列にマージソートを実施
    :
```

### 4. 分割したソート済み配列にマージソートを実施

　マージについては、一般的なマージソートの手順と同じです。
　既に分割済みのため、**マージ作業だけ**で十分なのです！イメージはこんな感じです。

![名称未設定.001.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/298123/dd9291cc-109e-e2cb-fa95-3fc85542cd1b.jpeg)

<details><summary>マージソートの関数（マージのみ）</summary><div>

```python
# マージソート(分割は未実施)を実施する関数
def mergeSort(arr, l, m, r):
    left, right = arr[l:m+1], arr[m+1:r+1]
    for i in range(l, r+1):
        if len(left) == 0:
            arr[i] = right.pop(0)
        elif len(right) == 0:
            arr[i] = left.pop(0)
        elif left[0] <= right[0]:
            arr[i] = left.pop(0)
        else:
            arr[i] = right.pop(0)
```

</div></details>

　先程のプログラムの続きを見ていきましょう！

```python
def timSort(arr):
    # 【STEP1】長さをもとにminRunを計算
    :
    # 【STEP2】サブ配列に分割(minRunの長さごとに繰り返し実行)
    :
        # 【STEP3】サブ配列内で挿入ソート実施 
        insertionSort(arr, start, end)

    # 変数size（マージされたサブ配列の要素数合計をカウント）を用意
    size = minRun
    while size < n:
        # マージする2つのサブ配列の左端のインデックスを取得
        for left in range(0, n, 2 * size):
            # マージする2つのサブ配列の中央のインデックスを取得
            mid = min(n - 1, left + size - 1)
            # マージする2つのサブ配列の右端インデックスを取得
            right = min((left + 2 * size - 1), (n - 1))
            # マージソート実施
            mergeSort(arr, left, mid, right)
        size = 2 * size
```

　以上が、PythonによるTimsortのシンプル実装となります。

　Timちゃん、シンプル実装でも複雑で難しいですね...（泣）