マージソートを非再帰型に書き直す３～もう限界かもしれない～

# はじめに

これまで下記の記事で GNU C ライブラリの `qsort` について勉強してきた。

- [GNU C Libraryのqsortはクイックソートではないの？ - Qiita](https://qiita.com/TETSURO1999/items/3eff3b6a5e3983630f3c)
- [最強コンパイラを使えばマージソートは遅くない？ - Qiita](https://qiita.com/TETSURO1999/items/0cc093f427531407d2d4)
- [マージソートを非再帰型に書き直す～誰でも思いつくアイディアだが～ - Qiita](https://qiita.com/TETSURO1999/items/23bdd493975cbd8a5085)
- [マージソートを非再帰型に書き直す２～さらなる改善を試みる～ - Qiita](https://qiita.com/TETSURO1999/items/783aa5732b9f19a615ca)

GNU C ライブラリの `qsort` はマージソートであり，再帰関数（トップダウン型）として作られていることから，非再帰型（ボトムアップ型）に書き直すことでパフォーマンスアップを狙ったが，期待したほどの効果（劇的な効果）を得られなかった。

そもそも明確な利点があったら GNU C ライブラリで採用しているだろうから，非再帰型（ボトムアップ型）には他に何か致命的な欠陥？があるのではないかと思うようになった。

# ボトムアップ型の課題その３

それは配列のサイズ $n$ に対して，計算量（比較回数）が不連続に変化してしまうことだと思われる。glibc のような再帰型（トップダウン型）のマージソートは計算量（比較回数）が綺麗に $O(n \log n)$ の直線上に乗るが，非再帰型（ボトムアップ型）のマージソートは $n$ が２のべき乗数のときのみ直線上に乗り，そこから $n$ が少し増えると直線から外れて急増してしまうのだ。

まずは一例を示そう。乱数データにおいて，再帰型と非再帰型のマージソートの比較関数の呼び出し回数の比較を以下に示す。配列のサイズ $n$ が２のべき乗のとき両者は一致しているが，そこから $n$ が僅かに増加すると非再帰型のほうは急増する。

<table>
<caption>表１　比較関数の呼び出し回数の比較</caption>
<thead>
<tr><th style="text-align:center">サイズ $n$</th>
    <th style="text-align:center">①再帰型</th>
    <th style="text-align:center">②非再帰型</th>
    <th style="text-align:center">②／①</th></tr>
</thead>
<tbody>
<tr><td style="text-align:right">256</td>
    <td style="text-align:right">1,710</td>
    <td style="text-align:right">1,710</td>
    <td style="text-align:right">1.000</td></tr>
<tr><td style="text-align:right">260</td>
    <td style="text-align:right">1,745</td>
    <td style="text-align:right">1,948</td>
    <td style="text-align:right">1.116</td></tr>
<tr><td style="text-align:right">512</td>
    <td style="text-align:right">3,955</td>
    <td style="text-align:right">3,955</td>
    <td style="text-align:right">1.000</td></tr>
<tr><td style="text-align:right">516</td>
    <td style="text-align:right">3,989</td>
    <td style="text-align:right">4,460</td>
    <td style="text-align:right">1.118</td></tr>
<tr><td style="text-align:right">1,024</td>
    <td style="text-align:right">8,919</td>
    <td style="text-align:right">8,919</td>
    <td style="text-align:right">1.000</td></tr>
<tr><td style="text-align:right">1,028</td>
    <td style="text-align:right">8,969</td>
    <td style="text-align:right">9,347</td>
    <td style="text-align:right">1.042</td></tr>
<tr><td style="text-align:right">2,048</td>
    <td style="text-align:right">19,934</td>
    <td style="text-align:right">19,934</td>
    <td style="text-align:right">1.000</td></tr>
<tr><td style="text-align:right">2,052</td>
    <td style="text-align:right">19,996</td>
    <td style="text-align:right">21,443</td>
    <td style="text-align:right">1.072</td></tr>
<tr><td style="text-align:right">4,096</td>
    <td style="text-align:right">43,949</td>
    <td style="text-align:right">43,949</td>
    <td style="text-align:right">1.000</td></tr>
<tr><td style="text-align:right">4,100</td>
    <td style="text-align:right">43,986</td>
    <td style="text-align:right">47,095</td>
    <td style="text-align:right">1.071</td></tr>
<tr><td style="text-align:right">8,192</td>
    <td style="text-align:right">96,168</td>
    <td style="text-align:right">96,168</td>
    <td style="text-align:right">1.000</td></tr>
<tr><td style="text-align:right">8,196</td>
    <td style="text-align:right">96,298</td>
    <td style="text-align:right">101,899</td>
    <td style="text-align:right">1.058</td></tr>
<tr><td style="text-align:right">16,384</td>
    <td style="text-align:right">208,716</td>
    <td style="text-align:right">208,716</td>
    <td style="text-align:right">1.000</td></tr>
<tr><td style="text-align:right">16,388</td>
    <td style="text-align:right">208,768</td>
    <td style="text-align:right">220,389</td>
    <td style="text-align:right">1.056</td></tr>
<tr><td style="text-align:right">32,768</td>
    <td style="text-align:right">450,090</td>
    <td style="text-align:right">450,090</td>
    <td style="text-align:right">1.000</td></tr>
<tr><td style="text-align:right">32,772</td>
    <td style="text-align:right">450,157</td>
    <td style="text-align:right">468,945</td>
    <td style="text-align:right">1.042</td></tr>
<tr><td style="text-align:right">65,536</td>
    <td style="text-align:right">965,855</td>
    <td style="text-align:right">965,855</td>
    <td style="text-align:right">1.000</td></tr>
<tr><td style="text-align:right">65,540</td>
    <td style="text-align:right">965,664</td>
    <td style="text-align:right">997,836</td>
    <td style="text-align:right">1.033</td></tr>
<tr><td style="text-align:right">131,072</td>
    <td style="text-align:right">2,062,821</td>
    <td style="text-align:right">2,062,821</td>
    <td style="text-align:right">1.000</td></tr>
<tr><td style="text-align:right">131,076</td>
    <td style="text-align:right">2,062,428</td>
    <td style="text-align:right">2,193,463</td>
    <td style="text-align:right">1.064</td></tr>
<tr><td style="text-align:right">262,144</td>
    <td style="text-align:right">4,387,074</td>
    <td style="text-align:right">4,387,074</td>
    <td style="text-align:right">1.000</td></tr>
<tr><td style="text-align:right">262,148</td>
    <td style="text-align:right">4,387,229</td>
    <td style="text-align:right">4,612,494</td>
    <td style="text-align:right">1.051</td></tr>
<tr><td style="text-align:right">524,288</td>
    <td style="text-align:right">9,299,238</td>
    <td style="text-align:right">9,299,238</td>
    <td style="text-align:right">1.000</td></tr>
<tr><td style="text-align:right">524,292</td>
    <td style="text-align:right">9,298,853</td>
    <td style="text-align:right">9,696,633</td>
    <td style="text-align:right">1.043</td></tr>
<tr><td style="text-align:right">1,048,576</td>
    <td style="text-align:right">19,645,708</td>
    <td style="text-align:right">19,645,708</td>
    <td style="text-align:right">1.000</td></tr>
<tr><td style="text-align:right">1,048,580</td>
    <td style="text-align:right">19,646,474</td>
    <td style="text-align:right">20,621,315</td>
    <td style="text-align:right">1.050</td></tr>
<tr><td style="text-align:right">2,097,152</td>
    <td style="text-align:right">41,387,613</td>
    <td style="text-align:right">41,387,613</td>
    <td style="text-align:right">1.000</td></tr>
<tr><td style="text-align:right">2,097,156</td>
    <td style="text-align:right">41,387,497</td>
    <td style="text-align:right">43,459,509</td>
    <td style="text-align:right">1.050</td></tr>
<tr><td style="text-align:right">4,194,304</td>
    <td style="text-align:right">86,970,643</td>
    <td style="text-align:right">86,970,643</td>
    <td style="text-align:right">1.000</td></tr>
<tr><td style="text-align:right">4,194,308</td>
    <td style="text-align:right">86,970,926</td>
    <td style="text-align:right">88,560,546</td>
    <td style="text-align:right">1.018</td></tr>
<tr><td style="text-align:right">8,388,608</td>
    <td style="text-align:right">182,330,408</td>
    <td style="text-align:right">182,330,408</td>
    <td style="text-align:right">1.000</td></tr>
<tr><td style="text-align:right">8,388,612</td>
    <td style="text-align:right">182,329,368</td>
    <td style="text-align:right">187,365,121</td>
    <td style="text-align:right">1.028</td></tr>
<tr><td style="text-align:right">16,777,216</td>
    <td style="text-align:right">381,440,754</td>
    <td style="text-align:right">381,440,754</td>
    <td style="text-align:right">1.000</td></tr>
<tr><td style="text-align:right">16,777,220</td>
    <td style="text-align:right">381,441,160</td>
    <td style="text-align:right">395,497,500</td>
    <td style="text-align:right">1.037</td></tr>
<tr><td style="text-align:right">33,554,432</td>
    <td style="text-align:right">796,435,814</td>
    <td style="text-align:right">796,435,814</td>
    <td style="text-align:right">1.000</td></tr>
<tr><td style="text-align:right">33,554,436</td>
    <td style="text-align:right">796,435,082</td>
    <td style="text-align:right">827,538,527</td>
    <td style="text-align:right">1.039</td></tr>
<tr><td style="text-align:right">67,108,864</td>
    <td style="text-align:right">1,659,965,763</td>
    <td style="text-align:right">1,659,965,763</td>
    <td style="text-align:right">1.000</td></tr>
<tr><td style="text-align:right">67,108,868</td>
    <td style="text-align:right">1,659,973,267</td>
    <td style="text-align:right">1,714,466,532</td>
    <td style="text-align:right">1.033</td></tr>
<tr><td style="text-align:right">134,217,728</td>
    <td style="text-align:right">3,454,152,093</td>
    <td style="text-align:right">3,454,152,093</td>
    <td style="text-align:right">1.000</td></tr>
<tr><td style="text-align:right">134,217,732</td>
    <td style="text-align:right">3,454,152,216</td>
    <td style="text-align:right">3,577,340,295</td>
    <td style="text-align:right">1.036</td></tr>
</tbody>
</table>

こういうのはグラフにすると分かり易い。※ e は envelope のことね。

<font color=#ED7D31>◆</font>②／①，<font color=#808080>■</font>包絡線 $e(n)$

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="650" height="480">
<g fill="lightgray">
<path d="M60 30  h550 v1 h-550">
<path d="M60 80  h550 v1 h-550">
<path d="M60 130 h550 v1 h-550">
<path d="M60 180 h550 v1 h-550">
<path d="M60 230 h550 v1 h-550">
<path d="M60 280 h550 v1 h-550">
<path d="M60 330 h550 v1 h-550">
<path d="M60 380 h550 v1 h-550">
<path d="M60 430 h550 v1 h-550">
<path d="M60  430 v-400 h1 v400">
<path d="M110 430 v-400 h1 v400">
<path d="M160 430 v-400 h1 v400">
<path d="M210 430 v-400 h1 v400">
<path d="M260 430 v-400 h1 v400">
<path d="M310 430 v-400 h1 v400">
<path d="M360 430 v-400 h1 v400">
<path d="M410 430 v-400 h1 v400">
<path d="M460 430 v-400 h1 v400">
<path d="M510 430 v-400 h1 v400">
<path d="M560 430 v-400 h1 v400">
<path d="M610 430 v-400 h1 v400">
</g>
<text x="16" y="35"  font-size="16" fill="black">1.14</text>
<text x="16" y="85"  font-size="16" fill="black">1.12</text>
<text x="16" y="135" font-size="16" fill="black">1.10</text>
<text x="16" y="185" font-size="16" fill="black">1.08</text>
<text x="16" y="235" font-size="16" fill="black">1.06</text>
<text x="16" y="285" font-size="16" fill="black">1.04</text>
<text x="16" y="335" font-size="16" fill="black">1.02</text>
<text x="16" y="385" font-size="16" fill="black">1.00</text>
<text x="16" y="435" font-size="16" fill="black">0.98</text>
<text x="51"  y="450" font-size="16" fill="black">2⁶</text>
<text x="101" y="450" font-size="16" fill="black">2⁸</text>
<text x="151" y="450" font-size="16" fill="black">2¹⁰</text>
<text x="201" y="450" font-size="16" fill="black">2¹²</text>
<text x="251" y="450" font-size="16" fill="black">2¹⁴</text>
<text x="301" y="450" font-size="16" fill="black">2¹⁶</text>
<text x="351" y="450" font-size="16" fill="black">2¹⁸</text>
<text x="401" y="450" font-size="16" fill="black">2²⁰</text>
<text x="451" y="450" font-size="16" fill="black">2²²</text>
<text x="501" y="450" font-size="16" fill="black">2²⁴</text>
<text x="551" y="450" font-size="16" fill="black">2²⁶</text>
<text x="601" y="450" font-size="16" fill="black">2²⁸</text>
<text x="260" y="470" font-size="16" fill="black">配列のサイズ</text>
<g fill="#808080">
<path d="M110 67.5 h42.8 v1 h-42.8" transform="rotate(54.2,110,67.5)">
<path d="M135 102.2 h37.4 v1 h-37.4" transform="rotate(48,135,102.2)">
<path d="M160 130 h33.8 v1 h-33.8" transform="rotate(42.3,160,130)">
<path d="M185 152.7 h31.4 v1 h-31.4" transform="rotate(37.1,185,152.7)">
<path d="M210 171.7 h29.7 v1 h-29.7" transform="rotate(32.7,210,171.7)">
<path d="M235 187.7 h28.5 v1 h-28.5" transform="rotate(28.8,235,187.7)">
<path d="M260 201.4 h27.7 v1 h-27.7" transform="rotate(25.5,260,201.4)">
<path d="M285 213.3 h27.1 v1 h-27.1" transform="rotate(22.6,285,213.3)">
<path d="M310 223.8 h26.6 v1 h-26.6" transform="rotate(20.2,310,223.8)">
<path d="M335 232.9 h26.3 v1 h-26.3" transform="rotate(18.1,335,232.9)">
<path d="M360 241.1 h26 v1 h-26" transform="rotate(16.3,360,241.1)">
<path d="M385 248.4 h25.9 v1 h-25.9" transform="rotate(14.7,385,248.4)">
<path d="M410 255 h25.7 v1 h-25.7" transform="rotate(13.4,410,255)">
<path d="M435 261 h25.6 v1 h-25.6" transform="rotate(12.2,435,261)">
<path d="M460 266.4 h25.5 v1 h-25.5" transform="rotate(11.2,460,266.4)">
<path d="M485 271.3 h25.4 v1 h-25.4" transform="rotate(10.3,485,271.3)">
<path d="M510 275.8 h25.3 v1 h-25.3" transform="rotate(9.5,510,275.8)">
<path d="M535 280 h25.3 v1 h-25.3" transform="rotate(8.7,535,280)">
<path d="M560 283.8 h25.3 v1 h-25.3" transform="rotate(8.1,560,283.8)">
</g>
<g fill="#ED7D31">
<path d="M110 374 l-6 6 l6 6 l6 -6">
<path d="M110.6 83.2 l-6 6 l6 6 l6 -6">
<path d="M135 374 l-6 6 l6 6 l6 -6">
<path d="M135.3 78.8 l-6 6 l6 6 l6 -6">
<path d="M160 374 l-6 6 l6 6 l6 -6">
<path d="M160.1 268.6 l-6 6 l6 6 l6 -6">
<path d="M185 374 l-6 6 l6 6 l6 -6">
<path d="M185.1 193.1 l-6 6 l6 6 l6 -6">
<path d="M210 374 l-6 6 l6 6 l6 -6">
<path d="M210 197.3 l-6 6 l6 6 l6 -6">
<path d="M235 374 l-6 6 l6 6 l6 -6">
<path d="M235 228.6 l-6 6 l6 6 l6 -6">
<path d="M260 374 l-6 6 l6 6 l6 -6">
<path d="M260 234.8 l-6 6 l6 6 l6 -6">
<path d="M285 374 l-6 6 l6 6 l6 -6">
<path d="M285 269.7 l-6 6 l6 6 l6 -6">
<path d="M310 374 l-6 6 l6 6 l6 -6">
<path d="M310 290.7 l-6 6 l6 6 l6 -6">
<path d="M335 374 l-6 6 l6 6 l6 -6">
<path d="M335 215.2 l-6 6 l6 6 l6 -6">
<path d="M360 374 l-6 6 l6 6 l6 -6">
<path d="M360 245.6 l-6 6 l6 6 l6 -6">
<path d="M385 374 l-6 6 l6 6 l6 -6">
<path d="M385 267.1 l-6 6 l6 6 l6 -6">
<path d="M410 374 l-6 6 l6 6 l6 -6">
<path d="M410 250 l-6 6 l6 6 l6 -6">
<path d="M435 374 l-6 6 l6 6 l6 -6">
<path d="M435 248.8 l-6 6 l6 6 l6 -6">
<path d="M460 374 l-6 6 l6 6 l6 -6">
<path d="M460 328.3 l-6 6 l6 6 l6 -6">
<path d="M485 374 l-6 6 l6 6 l6 -6">
<path d="M485 305 l-6 6 l6 6 l6 -6">
<path d="M510 374 l-6 6 l6 6 l6 -6">
<path d="M510 281.9 l-6 6 l6 6 l6 -6">
<path d="M535 374 l-6 6 l6 6 l6 -6">
<path d="M535 276.4 l-6 6 l6 6 l6 -6">
<path d="M560 374 l-6 6 l6 6 l6 -6">
<path d="M560 291.9 l-6 6 l6 6 l6 -6">
<path d="M585 374 l-6 6 l6 6 l6 -6">
<path d="M585 284.8 l-6 6 l6 6 l6 -6">
</g>
</svg>
title
<$FIGURE>
図１　比較関数の呼び出し回数の比
end title
@enduml
```

非再帰型と再帰型の呼び出し回数の比（②／①）の包絡線 $e(n)$ は配列のサイズ $n$ に対して

```math
e(n) \approx \frac{\log_2{n} + 1}{\log_2{n}}
```

になると考えられる。メカニズムは簡単で，配列のサイズ $n$ が２のべき乗数であれば，ボトムアップ型マージソートはちょうど $n$ 個のデータのマージを $\log_2{n}$ 段繰り返せば終わる。計算量が $O(n \log n)$ になるというのも分かり易い。 しかし，$n$ が一つ増えただけでマージする段数は一つ増えてしまうのだ。

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="700" height="326">
<g fill="magenta">
<path d="M144 100 l-10 12 h6 v12 h8 v-12 h6 l-10 -12">
<path d="M144 148 l-10 12 h6 v12 h8 v-12 h6 l-10 -12">
<path d="M144 196 l-10 12 h6 v12 h8 v-12 h6 l-10 -12">
<path d="M144 244 l-10 12 h6 v12 h8 v-12 h6 l-10 -12">
</g>
<g fill="black">
<path d="M16   80 h256 v1 h-256">
<path d="M16   96 h256 v1 h-256">
<path d="M16   80 v16 h1 v-16">
<path d="M272  80 v16 h1 v-16">
<path d="M16  128 h256 v1 h-256">
<path d="M16  144 h256 v1 h-256">
<path d="M16  128 v16 h1 v-16">
<path d="M144 128 v16 h1 v-16">
<path d="M272 128 v16 h1 v-16">
<path d="M16  176 h256 v1 h-256">
<path d="M16  192 h256 v1 h-256">
<path d="M16  176 v16 h1 v-16">
<path d="M80  176 v16 h1 v-16">
<path d="M144 176 v16 h1 v-16">
<path d="M208 176 v16 h1 v-16">
<path d="M272 176 v16 h1 v-16">
<path d="M16  224 h256 v1 h-256">
<path d="M16  240 h256 v1 h-256">
<path d="M16  224 v16 h1 v-16">
<path d="M48  224 v16 h1 v-16">
<path d="M80  224 v16 h1 v-16">
<path d="M112 224 v16 h1 v-16">
<path d="M144 224 v16 h1 v-16">
<path d="M176 224 v16 h1 v-16">
<path d="M208 224 v16 h1 v-16">
<path d="M240 224 v16 h1 v-16">
<path d="M272 224 v16 h1 v-16">
<path d="M16  272 h256 v1 h-256">
<path d="M16  288 h256 v1 h-256">
<path d="M16  272 v16 h1 v-16">
<path d="M32  272 v16 h1 v-16">
<path d="M48  272 v16 h1 v-16">
<path d="M64  272 v16 h1 v-16">
<path d="M80  272 v16 h1 v-16">
<path d="M96  272 v16 h1 v-16">
<path d="M112 272 v16 h1 v-16">
<path d="M128 272 v16 h1 v-16">
<path d="M144 272 v16 h1 v-16">
<path d="M160 272 v16 h1 v-16">
<path d="M176 272 v16 h1 v-16">
<path d="M192 272 v16 h1 v-16">
<path d="M208 272 v16 h1 v-16">
<path d="M224 272 v16 h1 v-16">
<path d="M240 272 v16 h1 v-16">
<path d="M256 272 v16 h1 v-16">
<path d="M272 272 v16 h1 v-16">
<path d="M16  304 h120 v1 h-120">
<path d="M272 304 h-120 v1 h120">
<path d="M16  304 v-8 h1 v8">
<path d="M272 304 v-8 h1 v8">
<path d="M288  80 h-8 v1 h8">
<path d="M288 288 h-8 v1 h8">
<path d="M288  80 v96 h1 v-96">
<path d="M288 288 v-96 h1 v96">
</g>
<g fill="magenta">
<path d="M472  52 l-10 12 h6 v12 h8 v-12 h6 l-10 -12">
<path d="M472 100 l-10 12 h6 v12 h8 v-12 h6 l-10 -12">
<path d="M472 148 l-10 12 h6 v12 h8 v-12 h6 l-10 -12">
<path d="M472 196 l-10 12 h6 v12 h8 v-12 h6 l-10 -12">
<path d="M472 244 l-10 12 h6 v12 h8 v-12 h6 l-10 -12">
</g>
<g fill="black">
<path d="M336  32 h272 v1 h-272">
<path d="M336  48 h272 v1 h-272">
<path d="M336  32 v16 h1 v-16">
<path d="M608  32 v16 h1 v-16">
<path d="M336  80 h272 v1 h-272">
<path d="M336  96 h272 v1 h-272">
<path d="M336  80 v16 h1 v-16">
<path d="M592  80 v16 h1 v-16">
<path d="M608  80 v16 h1 v-16">
<path d="M336 128 h272 v1 h-272">
<path d="M336 144 h272 v1 h-272">
<path d="M336 128 v16 h1 v-16">
<path d="M464 128 v16 h1 v-16">
<path d="M592 128 v16 h1 v-16">
<path d="M608 128 v16 h1 v-16">
<path d="M336 176 h272 v1 h-272">
<path d="M336 192 h272 v1 h-272">
<path d="M336 176 v16 h1 v-16">
<path d="M400 176 v16 h1 v-16">
<path d="M464 176 v16 h1 v-16">
<path d="M528 176 v16 h1 v-16">
<path d="M592 176 v16 h1 v-16">
<path d="M608 176 v16 h1 v-16">
<path d="M336 224 h272 v1 h-272">
<path d="M336 240 h272 v1 h-272">
<path d="M336 224 v16 h1 v-16">
<path d="M368 224 v16 h1 v-16">
<path d="M400 224 v16 h1 v-16">
<path d="M432 224 v16 h1 v-16">
<path d="M464 224 v16 h1 v-16">
<path d="M496 224 v16 h1 v-16">
<path d="M528 224 v16 h1 v-16">
<path d="M560 224 v16 h1 v-16">
<path d="M592 224 v16 h1 v-16">
<path d="M608 224 v16 h1 v-16">
<path d="M336 272 h272 v1 h-272">
<path d="M336 288 h272 v1 h-272">
<path d="M336 272 v16 h1 v-16">
<path d="M352 272 v16 h1 v-16">
<path d="M368 272 v16 h1 v-16">
<path d="M384 272 v16 h1 v-16">
<path d="M400 272 v16 h1 v-16">
<path d="M416 272 v16 h1 v-16">
<path d="M432 272 v16 h1 v-16">
<path d="M448 272 v16 h1 v-16">
<path d="M464 272 v16 h1 v-16">
<path d="M480 272 v16 h1 v-16">
<path d="M496 272 v16 h1 v-16">
<path d="M512 272 v16 h1 v-16">
<path d="M528 272 v16 h1 v-16">
<path d="M544 272 v16 h1 v-16">
<path d="M560 272 v16 h1 v-16">
<path d="M576 272 v16 h1 v-16">
<path d="M592 272 v16 h1 v-16">
<path d="M608 272 v16 h1 v-16">
<path d="M336 304 h112 v1 h-112">
<path d="M608 304 h-112 v1 h112">
<path d="M336 304 v-8 h1 v8">
<path d="M608 304 v-8 h1 v8">
<path d="M624  32 h-8 v1 h8">
<path d="M624 288 h-8 v1 h8">
<path d="M624  32 v122 h1 v-122">
<path d="M624 288 v-118 h1 v118">
</g>
<text x="136" y="310" font-size="16" fill="black">ｎ</text>
<text x="280" y="190" font-size="16" fill="black">log₂ｎ</text>
<text x="448" y="310" font-size="16" fill="black">ｎ＋１</text>
<text x="616" y="168" font-size="16" fill="black">log₂ｎ＋1</text>
</svg>
title
<$FIGURE>
図２　ボトムアップ型マージソートの場合
end title
@enduml
```

一方，トップダウン型の場合，配列のサイズ $n$ が一つ増えてもマージする段数が増えるのは一部の区間のみであり，全体には影響を及ぼさない。

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="700" height="326">
<g fill="magenta">
<path d="M144  76 l-10 -12 h6 v-12 h8 v12 h6 l-10 12">
<path d="M144 124 l-10 -12 h6 v-12 h8 v12 h6 l-10 12">
<path d="M144 172 l-10 -12 h6 v-12 h8 v12 h6 l-10 12">
<path d="M144 220 l-10 -12 h6 v-12 h8 v12 h6 l-10 12">
</g>
<g fill="black">
<path d="M16   32 h256 v1 h-256">
<path d="M16   48 h256 v1 h-256">
<path d="M16   32 v16 h1 v-16">
<path d="M272  32 v16 h1 v-16">
<path d="M16   80 h256 v1 h-256">
<path d="M16   96 h256 v1 h-256">
<path d="M16   80 v16 h1 v-16">
<path d="M144  80 v16 h1 v-16">
<path d="M272  80 v16 h1 v-16">
<path d="M16  128 h256 v1 h-256">
<path d="M16  144 h256 v1 h-256">
<path d="M16  128 v16 h1 v-16">
<path d="M80  128 v16 h1 v-16">
<path d="M144 128 v16 h1 v-16">
<path d="M208 128 v16 h1 v-16">
<path d="M272 128 v16 h1 v-16">
<path d="M16  176 h256 v1 h-256">
<path d="M16  192 h256 v1 h-256">
<path d="M16  176 v16 h1 v-16">
<path d="M48  176 v16 h1 v-16">
<path d="M80  176 v16 h1 v-16">
<path d="M112 176 v16 h1 v-16">
<path d="M144 176 v16 h1 v-16">
<path d="M176 176 v16 h1 v-16">
<path d="M208 176 v16 h1 v-16">
<path d="M240 176 v16 h1 v-16">
<path d="M272 176 v16 h1 v-16">
<path d="M16  224 h256 v1 h-256">
<path d="M16  240 h256 v1 h-256">
<path d="M16  224 v16 h1 v-16">
<path d="M32  224 v16 h1 v-16">
<path d="M48  224 v16 h1 v-16">
<path d="M64  224 v16 h1 v-16">
<path d="M80  224 v16 h1 v-16">
<path d="M96  224 v16 h1 v-16">
<path d="M112 224 v16 h1 v-16">
<path d="M128 224 v16 h1 v-16">
<path d="M144 224 v16 h1 v-16">
<path d="M160 224 v16 h1 v-16">
<path d="M176 224 v16 h1 v-16">
<path d="M192 224 v16 h1 v-16">
<path d="M208 224 v16 h1 v-16">
<path d="M224 224 v16 h1 v-16">
<path d="M240 224 v16 h1 v-16">
<path d="M256 224 v16 h1 v-16">
<path d="M272 224 v16 h1 v-16">
<path d="M16  256 h120 v1 h-120">
<path d="M272 256 h-120 v1 h120">
<path d="M16  256 v-8 h1 v8">
<path d="M272 256 v-8 h1 v8">
<path d="M288  32 h-8 v1 h8">
<path d="M288 240 h-8 v1 h8">
<path d="M288  32 v96 h1 v-96">
<path d="M288 240 v-96 h1 v96">
</g>
<g fill="magenta">
<path d="M472  76 l-10 -12 h6 v-12 h8 v12 h6 l-10 12">
<path d="M472 124 l-10 -12 h6 v-12 h8 v12 h6 l-10 12">
<path d="M472 172 l-10 -12 h6 v-12 h8 v12 h6 l-10 12">
<path d="M472 220 l-10 -12 h6 v-12 h8 v12 h6 l-10 12">
<path d="M592 268 l-10 -12 h6 v-12 h8 v12 h6 l-10 12">
</g>
<g fill="black">
<path d="M336  32 h272 v1 h-272">
<path d="M336  48 h272 v1 h-272">
<path d="M336  32 v16 h1 v-16">
<path d="M608  32 v16 h1 v-16">
<path d="M336  80 h272 v1 h-272">
<path d="M336  96 h272 v1 h-272">
<path d="M336  80 v16 h1 v-16">
<path d="M464  80 v16 h1 v-16">
<path d="M608  80 v16 h1 v-16">
<path d="M336 128 h272 v1 h-272">
<path d="M336 144 h272 v1 h-272">
<path d="M336 128 v16 h1 v-16">
<path d="M400 128 v16 h1 v-16">
<path d="M464 128 v16 h1 v-16">
<path d="M528 128 v16 h1 v-16">
<path d="M608 128 v16 h1 v-16">
<path d="M336 176 h272 v1 h-272">
<path d="M336 192 h272 v1 h-272">
<path d="M336 176 v16 h1 v-16">
<path d="M368 176 v16 h1 v-16">
<path d="M400 176 v16 h1 v-16">
<path d="M432 176 v16 h1 v-16">
<path d="M464 176 v16 h1 v-16">
<path d="M496 176 v16 h1 v-16">
<path d="M528 176 v16 h1 v-16">
<path d="M560 176 v16 h1 v-16">
<path d="M608 176 v16 h1 v-16">
<path d="M336 224 h272 v1 h-272">
<path d="M336 240 h272 v1 h-272">
<path d="M336 224 v16 h1 v-16">
<path d="M352 224 v16 h1 v-16">
<path d="M368 224 v16 h1 v-16">
<path d="M384 224 v16 h1 v-16">
<path d="M400 224 v16 h1 v-16">
<path d="M416 224 v16 h1 v-16">
<path d="M432 224 v16 h1 v-16">
<path d="M448 224 v16 h1 v-16">
<path d="M464 224 v16 h1 v-16">
<path d="M480 224 v16 h1 v-16">
<path d="M496 224 v16 h1 v-16">
<path d="M512 224 v16 h1 v-16">
<path d="M528 224 v16 h1 v-16">
<path d="M544 224 v16 h1 v-16">
<path d="M560 224 v16 h1 v-16">
<path d="M576 224 v16 h1 v-16">
<path d="M608 224 v16 h1 v-16">
<path d="M576 272 h32 v1 h-32">
<path d="M576 288 h32 v1 h-32">
<path d="M576 272 v16 h1 v-16">
<path d="M592 272 v16 h1 v-16">
<path d="M608 272 v16 h1 v-16">
<path d="M336 304 h112 v1 h-112">
<path d="M608 304 h-112 v1 h112">
<path d="M336 304 v-8 h1 v8">
<path d="M608 304 v-8 h1 v8">
<path d="M624  32 h-8 v1 h8">
<path d="M624 240 h-8 v1 h8">
<path d="M624  32 v96 h1 v-96">
<path d="M624 240 v-96 h1 v96">
</g>
<text x="136" y="262" font-size="16" fill="black">ｎ</text>
<text x="280" y="142" font-size="16" fill="black">log₂ｎ</text>
<text x="448" y="310" font-size="16" fill="black">ｎ＋１</text>
<text x="616" y="142" font-size="16" fill="black">log₂ｎ</text>
<text x="616" y="286" font-size="16" fill="black">＋１</text>
</svg>
title
<$FIGURE>
図３　トップダウン型マージソートの場合
end title
@enduml
```

# 実測するとどうなるか？

## 試験条件

- int 型の配列の昇順ソートを行う。配列のサイズは① 2²⁷ 個と② 2²⁷ + 2 個，③ 2²⁷ + 2² 個の三種類とし，実行時間の変化率②／①，③／①を比較する。
- 配列は乱数で初期化する。乱数発生器は XorShift とした。
- Cコンパイラは下記の三種類とし，かつターゲットを 32bit (x86)と64bit (x64)の二種類の組み合わせで合計六種類とする。
  - Microsoft Visual C++ 2022
  - LLVM clang 17.0.3
  - intel C++ compiler：oneAPI 2024.2, Compiler Release 2024.2.1
- 評価マシンのスペックは下記の通り。
  Windows10 2022H2，Core i7-13700 5.1GHZ，32GB
- 対象の比較関数は以下の通り。
  - glibc：再帰型（トップダウン型）マージソート，GNU C ライブラリの `qsort` の意訳版
  - merge：非再帰型（ボトムアップ型）マージソート，
    未結合要素は末尾
  - merge2：非再帰型（ボトムアップ型）マージソート，
    未結合要素は先頭（バックワード型）※今回作成
  - merge3：非再帰型（ボトムアップ型）マージソート，
    未結合要素は先頭（フォワード型）※今回作成

## 試験結果

試験結果を以下に示す。なお，測定のたびに実行時間は揺らぐため，同一条件で五回測定し，その最小値を示す。

<table>
<caption>表３　実行時間の比較（単位は秒）</caption>
<thead>
<tr><th style="text-align:center">コンパイラ</th>
    <th style="text-align:center">要素数</th>
    <th style="text-align:center">glibc</th>
    <th style="text-align:center">merge</th>
    <th style="text-align:center">merge2</th>
    <th style="text-align:center">merge3</th></tr>
</thead>
<tbody>
<tr></tr>
<tr><th rowspan=5>Visual C++<br>32bit版</th>
    <td>① 2²⁷</td>
    <td style="text-align:right">11.859</td>
    <td style="text-align:right">12.808</td>
    <td style="text-align:right">13.143</td>
    <td style="text-align:right">11.462</td></tr>
<tr></tr>
<tr><td>② 2²⁷ + 2</td>
    <td style="text-align:right">11.872</td>
    <td style="text-align:right">13.020</td>
    <td style="text-align:right">13.183</td>
    <td style="text-align:right">11.553</td></tr>
<tr></tr>
<tr><td>③ 2²⁷ + 2²</td>
    <td style="text-align:right">11.862</td>
    <td style="text-align:right">13.040</td>
    <td style="text-align:right">13.247</td>
    <td style="text-align:right">11.625</td></tr>
<tr></tr>
<tr><th rowspan=5>Visual C++<br>64bit版</th>
    <td>① 2²⁷</td>
    <td style="text-align:right">13.943</td>
    <td style="text-align:right">13.268</td>
    <td style="text-align:right">13.316</td>
    <td style="text-align:right">13.255</td></tr>
<tr></tr>
<tr><td>② 2²⁷ + 2</td>
    <td style="text-align:right">13.915</td>
    <td style="text-align:right">13.351</td>
    <td style="text-align:right">13.371</td>
    <td style="text-align:right">13.294</td></tr>
<tr></tr>
<tr><td>③ 2²⁷ + 2²</td>
    <td style="text-align:right">13.910</td>
    <td style="text-align:right">13.362</td>
    <td style="text-align:right">13.388</td>
    <td style="text-align:right">13.359</td></tr>
<tr></tr>
<tr><th rowspan=5>LLVM clang-cl<br>32bit版</th>
    <td>① 2²⁷</td>
    <td style="text-align:right">10.764</td>
    <td style="text-align:right">10.554</td>
    <td style="text-align:right">10.721</td>
    <td style="text-align:right">10.498</td></tr>
<tr></tr>
<tr><td>② 2²⁷ + 2</td>
    <td style="text-align:right">10.769</td>
    <td style="text-align:right">10.683</td>
    <td style="text-align:right">10.802</td>
    <td style="text-align:right">10.579</td></tr>
<tr></tr>
<tr><td>③ 2²⁷ + 2²</td>
    <td style="text-align:right">10.787</td>
    <td style="text-align:right">10.674</td>
    <td style="text-align:right">10.875</td>
    <td style="text-align:right">10.639</td></tr>
<tr></tr>
<tr><th rowspan=5>LLVM clang-cl<br>64bit版</th>
    <td>① 2²⁷</td>
    <td style="text-align:right">10.487</td>
    <td style="text-align:right">10.471</td>
    <td style="text-align:right">10.529</td>
    <td style="text-align:right">10.247</td></tr>
<tr></tr>
<tr><td>② 2²⁷ + 2</td>
    <td style="text-align:right">10.500</td>
    <td style="text-align:right">10.587</td>
    <td style="text-align:right">10.598</td>
    <td style="text-align:right">10.312</td></tr>
<tr></tr>
<tr><td>③ 2²⁷ + 2²</td>
    <td style="text-align:right">10.502</td>
    <td style="text-align:right">10.584</td>
    <td style="text-align:right">10.652</td>
    <td style="text-align:right">10.339</td></tr>
<tr></tr>
<tr><th rowspan=5>intel icx-cl<br>32bit版</th>
    <td>① 2²⁷</td>
    <td style="text-align:right">11.629</td>
    <td style="text-align:right">11.714</td>
    <td style="text-align:right">11.279</td>
    <td style="text-align:right">11.620</td></tr>
<tr></tr>
<tr><td>② 2²⁷ + 2</td>
    <td style="text-align:right">11.666</td>
    <td style="text-align:right">11.846</td>
    <td style="text-align:right">11.416</td>
    <td style="text-align:right">11.739</td></tr>
<tr></tr>
<tr><td>③ 2²⁷ + 2²</td>
    <td style="text-align:right">11.664</td>
    <td style="text-align:right">11.889</td>
    <td style="text-align:right">11.374</td>
    <td style="text-align:right">11.719</td></tr>
<tr></tr>
<tr><th rowspan=5>intel icx-cl<br>64bit版</th>
    <td>① 2²⁷</td>
    <td style="text-align:right">10.474</td>
    <td style="text-align:right">10.364</td>
    <td style="text-align:right">10.224</td>
    <td style="text-align:right">10.364</td></tr>
<tr></tr>
<tr><td>② 2²⁷ + 2</td>
    <td style="text-align:right">10.483</td>
    <td style="text-align:right">10.417</td>
    <td style="text-align:right">10.278</td>
    <td style="text-align:right">10.434</td></tr>
<tr></tr>
<tr><td>③ 2²⁷ + 2²</td>
    <td style="text-align:right">10.506</td>
    <td style="text-align:right">10.440</td>
    <td style="text-align:right">10.311</td>
    <td style="text-align:right">10.437</td></tr>
</tbody>
</table>

<table>
<caption>表４　実行時間の変化率</caption>
<thead>
<tr><th style="text-align:center">コンパイラ</th>
    <th style="text-align:center">要素数</th>
    <th style="text-align:center">glibc</th>
    <th style="text-align:center">merge</th>
    <th style="text-align:center">merge2</th>
    <th style="text-align:center">merge3</th></tr>
</thead>
<tbody>
<tr></tr>
<tr><th rowspan=3>Visual C++<br>32bit版</th>
    <td>②／①</td>
    <td style="text-align:right">1.0011</td>
    <td style="text-align:right">1.0166</td>
    <td style="text-align:right">1.0030</td>
    <td style="text-align:right">1.0079</td></tr>
<tr></tr>
<tr><td>③／①</td>
    <td style="text-align:right">1.0003</td>
    <td style="text-align:right">1.0181</td>
    <td style="text-align:right">1.0079</td>
    <td style="text-align:right">1.0142</td></tr>
<tr></tr>
<tr><th rowspan=3>Visual C++<br>64bit版</th>
    <td style="text-align:right">②／①</td>
    <td style="text-align:right">0.9980</td>
    <td style="text-align:right">1.0063</td>
    <td style="text-align:right">1.0041</td>
    <td style="text-align:right">1.0029</td></tr>
<tr></tr>
<tr><td style="text-align:right">③／①</td>
    <td style="text-align:right">0.9976</td>
    <td style="text-align:right">1.0071</td>
    <td style="text-align:right">1.0054</td>
    <td style="text-align:right">1.0078</td></tr>
<tr></tr>
<tr><th rowspan=3>LLVM clang-cl<br>32bit版</th>
    <td>②／①</td>
    <td style="text-align:right">1.0005</td>
    <td style="text-align:right">1.0122</td>
    <td style="text-align:right">1.0076</td>
    <td style="text-align:right">1.0077</td></tr>
<tr></tr>
<tr><td>③／①</td>
    <td style="text-align:right">1.0021</td>
    <td style="text-align:right">1.0114</td>
    <td style="text-align:right">1.0144</td>
    <td style="text-align:right">1.0134</td></tr>
<tr></tr>
<tr><th rowspan=3>LLVM clang-cl<br>64bit版</th>
    <td>②／①</td>
    <td style="text-align:right">1.0012</td>
    <td style="text-align:right">1.0111</td>
    <td style="text-align:right">1.0066</td>
    <td style="text-align:right">1.0063</td></tr>
<tr></tr>
<tr><td>③／①</td>
    <td style="text-align:right">1.0014</td>
    <td style="text-align:right">1.0108</td>
    <td style="text-align:right">1.0117</td>
    <td style="text-align:right">1.0090</td></tr>
<tr></tr>
<tr><th rowspan=3>intel icx-cl<br>32bit版</th>
    <td>②／①</td>
    <td style="text-align:right">1.0032</td>
    <td style="text-align:right">1.0113</td>
    <td style="text-align:right">1.0121</td>
    <td style="text-align:right">1.0102</td></tr>
<tr></tr>
<tr><td>③／①</td>
    <td style="text-align:right">1.0030</td>
    <td style="text-align:right">1.0149</td>
    <td style="text-align:right">1.0084</td>
    <td style="text-align:right">1.0085</td></tr>
<tr></tr>
<tr><th rowspan=3>intel icx-cl<br>64bit版</th>
    <td>②／①</td>
    <td style="text-align:right">1.0009</td>
    <td style="text-align:right">1.0051</td>
    <td style="text-align:right">1.0053</td>
    <td style="text-align:right">1.0068</td></tr>
<tr></tr>
<tr><td>③／①</td>
    <td style="text-align:right">1.0031</td>
    <td style="text-align:right">1.0073</td>
    <td style="text-align:right">1.0085</td>
    <td style="text-align:right">1.0070</td></tr>
</tbody>
</table>

こういうのはグラフにすると一目瞭然である。glibc は予想通り，要素数の変化に対して実行時間の変化が最小である。

<font color=#ED7D31>◆</font>glibc，<font color=#5B9BD5>◆</font>merge，<font color=#A5A5A5>◆</font>merge2，<font color=#FFC000>◆</font>merge3

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="340" height="360">
<g fill="lightgray">
<path d="M50 30 h280 v1 h-280">
<path d="M50 90 h280 v1 h-280">
<path d="M50 150 h280 v1 h-280">
<path d="M50 210 h280 v1 h-280">
<path d="M50 270 h280 v1 h-280">
<path d="M50 330 h280 v1 h-280">
</g>
<text x="7" y="36" font-size="14" fill="black">1.020</text>
<text x="7" y="96" font-size="14" fill="black">1.015</text>
<text x="7" y="156" font-size="14" fill="black">1.010</text>
<text x="7" y="216" font-size="14" fill="black">1.005</text>
<text x="7" y="276" font-size="14" fill="black">1.000</text>
<text x="7" y="336" font-size="14" fill="black">0.995</text>
<text x="90" y="350" font-size="14" fill="black">2²⁷</text>
<text x="163" y="350" font-size="14" fill="black">2²⁷+2</text>
<text x="256" y="350" font-size="14" fill="black">2²⁷+2²</text>
<g fill="#ED7D31">
<path d="M96.7 269 h94.3 v2 h-94.3" transform="rotate(-8,96.7,270)">
<path d="M190 255.8 h93.9 v2 h-93.9" transform="rotate(6.2,190,256.8)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 250.8 l-6 6 l6 6 l6 -6">
<path d="M283.3 261 l-6 6 l6 6 l6 -6">
</g>
<g fill="#5B9BD5">
<path d="M96.7 269 h219.5 v2 h-219.5" transform="rotate(-64.8,96.7,270)">
<path d="M190 70.4 h95.2 v2 h-95.2" transform="rotate(-11.4,190,71.4)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 65.4 l-6 6 l6 6 l6 -6">
<path d="M283.3 46.6 l-6 6 l6 6 l6 -6">
</g>
<g fill="#A5A5A5">
<path d="M96.7 269 h100.2 v2 h-100.2" transform="rotate(-21.4,96.7,270)">
<path d="M190 232.5 h110.1 v2 h-110.1" transform="rotate(-32,190,233.5)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 227.5 l-6 6 l6 6 l6 -6">
<path d="M283.3 169 l-6 6 l6 6 l6 -6">
</g>
<g fill="#FFC000">
<path d="M96.7 269 h133.4 v2 h-133.4" transform="rotate(-45.6,96.7,270)">
<path d="M190 173.7 h120 v2 h-120" transform="rotate(-38.9,190,174.7)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 168.7 l-6 6 l6 6 l6 -6">
<path d="M283.3 93.3 l-6 6 l6 6 l6 -6">
</g>
</svg>
title
<$FIGURE>
図４　Visual C++ 32bit版
end title
@enduml
```

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="340" height="360">
<g fill="lightgray">
<path d="M50 30 h280 v1 h-280">
<path d="M50 90 h280 v1 h-280">
<path d="M50 150 h280 v1 h-280">
<path d="M50 210 h280 v1 h-280">
<path d="M50 270 h280 v1 h-280">
<path d="M50 330 h280 v1 h-280">
</g>
<text x="7" y="36" font-size="14" fill="black">1.020</text>
<text x="7" y="96" font-size="14" fill="black">1.015</text>
<text x="7" y="156" font-size="14" fill="black">1.010</text>
<text x="7" y="216" font-size="14" fill="black">1.005</text>
<text x="7" y="276" font-size="14" fill="black">1.000</text>
<text x="7" y="336" font-size="14" fill="black">0.995</text>
<text x="90" y="350" font-size="14" fill="black">2²⁷</text>
<text x="163" y="350" font-size="14" fill="black">2²⁷+2</text>
<text x="256" y="350" font-size="14" fill="black">2²⁷+2²</text>
<g fill="#ED7D31">
<path d="M96.7 269 h96.4 v2 h-96.4" transform="rotate(14.5,96.7,270)">
<path d="M190 293.1 h93.4 v2 h-93.4" transform="rotate(2.6,190,294.1)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 288.1 l-6 6 l6 6 l6 -6">
<path d="M283.3 292.4 l-6 6 l6 6 l6 -6">
</g>
<g fill="#5B9BD5">
<path d="M96.7 269 h119.8 v2 h-119.8" transform="rotate(-38.8,96.7,270)">
<path d="M190 193.9 h93.9 v2 h-93.9" transform="rotate(-6.1,190,194.9)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 188.9 l-6 6 l6 6 l6 -6">
<path d="M283.3 179 l-6 6 l6 6 l6 -6">
</g>
<g fill="#A5A5A5">
<path d="M96.7 269 h105.7 v2 h-105.7" transform="rotate(-28,96.7,270)">
<path d="M190 219.4 h94.6 v2 h-94.6" transform="rotate(-9.3,190,220.4)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 214.4 l-6 6 l6 6 l6 -6">
<path d="M283.3 199.1 l-6 6 l6 6 l6 -6">
</g>
<g fill="#FFC000">
<path d="M96.7 269 h99.8 v2 h-99.8" transform="rotate(-20.7,96.7,270)">
<path d="M190 233.7 h110.3 v2 h-110.3" transform="rotate(-32.2,190,234.7)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 228.7 l-6 6 l6 6 l6 -6">
<path d="M283.3 169.8 l-6 6 l6 6 l6 -6">
</g>
</svg>
title
<$FIGURE>
図５　Visual C++ 64bit版
end title
@enduml
```

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="340" height="360">
<g fill="lightgray">
<path d="M50 30 h280 v1 h-280">
<path d="M50 90 h280 v1 h-280">
<path d="M50 150 h280 v1 h-280">
<path d="M50 210 h280 v1 h-280">
<path d="M50 270 h280 v1 h-280">
<path d="M50 330 h280 v1 h-280">
</g>
<text x="7" y="36" font-size="14" fill="black">1.020</text>
<text x="7" y="96" font-size="14" fill="black">1.015</text>
<text x="7" y="156" font-size="14" fill="black">1.010</text>
<text x="7" y="216" font-size="14" fill="black">1.005</text>
<text x="7" y="276" font-size="14" fill="black">1.000</text>
<text x="7" y="336" font-size="14" fill="black">0.995</text>
<text x="90" y="350" font-size="14" fill="black">2²⁷</text>
<text x="163" y="350" font-size="14" fill="black">2²⁷+2</text>
<text x="256" y="350" font-size="14" fill="black">2²⁷+2²</text>
<g fill="#ED7D31">
<path d="M96.7 269 h93.5 v2 h-93.5" transform="rotate(-3.4,96.7,270)">
<path d="M190 263.4 h95.5 v2 h-95.5" transform="rotate(-12.1,190,264.4)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 258.4 l-6 6 l6 6 l6 -6">
<path d="M283.3 238.4 l-6 6 l6 6 l6 -6">
</g>
<g fill="#5B9BD5">
<path d="M96.7 269 h173.9 v2 h-173.9" transform="rotate(-57.5,96.7,270)">
<path d="M190 122.3 h93.9 v2 h-93.9" transform="rotate(6.3,190,123.3)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 117.3 l-6 6 l6 6 l6 -6">
<path d="M283.3 127.6 l-6 6 l6 6 l6 -6">
</g>
<g fill="#A5A5A5">
<path d="M96.7 269 h130.1 v2 h-130.1" transform="rotate(-44.2,96.7,270)">
<path d="M190 178.3 h124 v2 h-124" transform="rotate(-41.2,190,179.3)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 173.3 l-6 6 l6 6 l6 -6">
<path d="M283.3 91.6 l-6 6 l6 6 l6 -6">
</g>
<g fill="#FFC000">
<path d="M96.7 269 h131.5 v2 h-131.5" transform="rotate(-44.8,96.7,270)">
<path d="M190 176.4 h115.8 v2 h-115.8" transform="rotate(-36.3,190,177.4)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 171.4 l-6 6 l6 6 l6 -6">
<path d="M283.3 102.8 l-6 6 l6 6 l6 -6">
</g>
</svg>
title
<$FIGURE>
図６　LLVM clang-cl 32bit版
end title
@enduml
```

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="340" height="360">
<g fill="lightgray">
<path d="M50 30 h280 v1 h-280">
<path d="M50 90 h280 v1 h-280">
<path d="M50 150 h280 v1 h-280">
<path d="M50 210 h280 v1 h-280">
<path d="M50 270 h280 v1 h-280">
<path d="M50 330 h280 v1 h-280">
</g>
<text x="7" y="36" font-size="14" fill="black">1.020</text>
<text x="7" y="96" font-size="14" fill="black">1.015</text>
<text x="7" y="156" font-size="14" fill="black">1.010</text>
<text x="7" y="216" font-size="14" fill="black">1.005</text>
<text x="7" y="276" font-size="14" fill="black">1.000</text>
<text x="7" y="336" font-size="14" fill="black">0.995</text>
<text x="90" y="350" font-size="14" fill="black">2²⁷</text>
<text x="163" y="350" font-size="14" fill="black">2²⁷+2</text>
<text x="256" y="350" font-size="14" fill="black">2²⁷+2²</text>
<g fill="#ED7D31">
<path d="M96.7 269 h94.5 v2 h-94.5" transform="rotate(-9.1,96.7,270)">
<path d="M190 254.1 h93.4 v2 h-93.4" transform="rotate(-1.4,190,255.1)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 249.1 l-6 6 l6 6 l6 -6">
<path d="M283.3 246.8 l-6 6 l6 6 l6 -6">
</g>
<g fill="#5B9BD5">
<path d="M96.7 269 h162.4 v2 h-162.4" transform="rotate(-54.9,96.7,270)">
<path d="M190 136.1 h93.4 v2 h-93.4" transform="rotate(2.1,190,137.1)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 131.1 l-6 6 l6 6 l6 -6">
<path d="M283.3 134.5 l-6 6 l6 6 l6 -6">
</g>
<g fill="#A5A5A5">
<path d="M96.7 269 h122 v2 h-122" transform="rotate(-40.1,96.7,270)">
<path d="M190 190.4 h111.8 v2 h-111.8" transform="rotate(-33.4,190,191.4)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 185.4 l-6 6 l6 6 l6 -6">
<path d="M283.3 123.8 l-6 6 l6 6 l6 -6">
</g>
<g fill="#FFC000">
<path d="M96.7 269 h120.4 v2 h-120.4" transform="rotate(-39.2,96.7,270)">
<path d="M190 192.9 h98.5 v2 h-98.5" transform="rotate(-18.7,190,193.9)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 187.9 l-6 6 l6 6 l6 -6">
<path d="M283.3 156.3 l-6 6 l6 6 l6 -6">
</g>
</svg>
title
<$FIGURE>
図７　LLVM clang-cl 64bit版
end title
@enduml
```

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="340" height="360">
<g fill="lightgray">
<path d="M50 30 h280 v1 h-280">
<path d="M50 90 h280 v1 h-280">
<path d="M50 150 h280 v1 h-280">
<path d="M50 210 h280 v1 h-280">
<path d="M50 270 h280 v1 h-280">
<path d="M50 330 h280 v1 h-280">
</g>
<text x="7" y="36" font-size="14" fill="black">1.020</text>
<text x="7" y="96" font-size="14" fill="black">1.015</text>
<text x="7" y="156" font-size="14" fill="black">1.010</text>
<text x="7" y="216" font-size="14" fill="black">1.005</text>
<text x="7" y="276" font-size="14" fill="black">1.000</text>
<text x="7" y="336" font-size="14" fill="black">0.995</text>
<text x="90" y="350" font-size="14" fill="black">2²⁷</text>
<text x="163" y="350" font-size="14" fill="black">2²⁷+2</text>
<text x="256" y="350" font-size="14" fill="black">2²⁷+2²</text>
<g fill="#ED7D31">
<path d="M96.7 269 h100.8 v2 h-100.8" transform="rotate(-22.2,96.7,270)">
<path d="M190 230.8 h93.4 v2 h-93.4" transform="rotate(1.3,190,231.8)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 225.8 l-6 6 l6 6 l6 -6">
<path d="M283.3 227.9 l-6 6 l6 6 l6 -6">
</g>
<g fill="#5B9BD5">
<path d="M96.7 269 h164.3 v2 h-164.3" transform="rotate(-55.4,96.7,270)">
<path d="M190 133.8 h103.2 v2 h-103.2" transform="rotate(-25.3,190,134.8)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 128.8 l-6 6 l6 6 l6 -6">
<path d="M283.3 84.7 l-6 6 l6 6 l6 -6">
</g>
<g fill="#A5A5A5">
<path d="M96.7 269 h173.1 v2 h-173.1" transform="rotate(-57.4,96.7,270)">
<path d="M190 123.2 h103.5 v2 h-103.5" transform="rotate(25.6,190,124.2)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 118.2 l-6 6 l6 6 l6 -6">
<path d="M283.3 162.9 l-6 6 l6 6 l6 -6">
</g>
<g fill="#FFC000">
<path d="M96.7 269 h154.3 v2 h-154.3" transform="rotate(-52.8,96.7,270)">
<path d="M190 146.1 h95.6 v2 h-95.6" transform="rotate(12.5,190,147.1)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 141.1 l-6 6 l6 6 l6 -6">
<path d="M283.3 161.8 l-6 6 l6 6 l6 -6">
</g>
</svg>
title
<$FIGURE>
図８　intel icx-cl 32bit版
end title
@enduml
```

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="340" height="360">
<g fill="lightgray">
<path d="M50 30 h280 v1 h-280">
<path d="M50 90 h280 v1 h-280">
<path d="M50 150 h280 v1 h-280">
<path d="M50 210 h280 v1 h-280">
<path d="M50 270 h280 v1 h-280">
<path d="M50 330 h280 v1 h-280">
</g>
<text x="7" y="36" font-size="14" fill="black">1.020</text>
<text x="7" y="96" font-size="14" fill="black">1.015</text>
<text x="7" y="156" font-size="14" fill="black">1.010</text>
<text x="7" y="216" font-size="14" fill="black">1.005</text>
<text x="7" y="276" font-size="14" fill="black">1.000</text>
<text x="7" y="336" font-size="14" fill="black">0.995</text>
<text x="90" y="350" font-size="14" fill="black">2²⁷</text>
<text x="163" y="350" font-size="14" fill="black">2²⁷+2</text>
<text x="256" y="350" font-size="14" fill="black">2²⁷+2²</text>
<g fill="#ED7D31">
<path d="M96.7 269 h93.9 v2 h-93.9" transform="rotate(-6.3,96.7,270)">
<path d="M190 258.7 h97 v2 h-97" transform="rotate(-15.8,190,259.7)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 253.7 l-6 6 l6 6 l6 -6">
<path d="M283.3 227.3 l-6 6 l6 6 l6 -6">
</g>
<g fill="#5B9BD5">
<path d="M96.7 269 h111.7 v2 h-111.7" transform="rotate(-33.3,96.7,270)">
<path d="M190 207.6 h97.1 v2 h-97.1" transform="rotate(-15.9,190,208.6)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 202.6 l-6 6 l6 6 l6 -6">
<path d="M283.3 176 l-6 6 l6 6 l6 -6">
</g>
<g fill="#A5A5A5">
<path d="M96.7 269 h112.8 v2 h-112.8" transform="rotate(-34.2,96.7,270)">
<path d="M190 205.6 h101.1 v2 h-101.1" transform="rotate(-22.5,190,206.6)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 200.6 l-6 6 l6 6 l6 -6">
<path d="M283.3 161.9 l-6 6 l6 6 l6 -6">
</g>
<g fill="#FFC000">
<path d="M96.7 269 h123.6 v2 h-123.6" transform="rotate(-41,96.7,270)">
<path d="M190 188 h93.4 v2 h-93.4" transform="rotate(-2.1,190,189)">
<path d="M96.7 264 l-6 6 l6 6 l6 -6">
<path d="M190 183 l-6 6 l6 6 l6 -6">
<path d="M283.3 179.5 l-6 6 l6 6 l6 -6">
</g>
</svg>
title
<$FIGURE>
図９　intel icx-cl 64bit版
end title
@enduml
```

# 結論

理論的と言うか簡易的な見積もり（包絡線）では計算量の増加は **3.9%** であったが，非再帰型（ボトムアップ型）マージソートとして実装した三種類のいずれとも実行時間の増加はせいぜい **2%** に抑えられている。

とはいえ，これは今回精度よく計億できるように配列の要素数を $2^{27}$ と巨大な値に設定したからであり，実際にはもっと小さなサイズで用いられることが多いだろう。たとえば配列の要素数が $2^{10}$ 程度では，２のべき乗数から外れると **10%** を超える計算量の増加が予測されており，実際の実行時間の増加が半分の **5%** 程度だとしても，非再帰型による改善効果（関数呼び出しのオーバーヘッド低減）を打ち消してしまうだろう。

以上より，GNU C ライブラリの開発者は `qsort` の実装として非再帰型（ボトムアップ型）マージソートを採用しないのではないかと考えている。

# 次回

次回に続く。

- [マージソートを非再帰型に書き直す４～限界突破のアイディアを思いつく～ - Qiita](https://qiita.com/TETSURO1999/items/17d751555fcf9b275518)