マージソートを非再帰型に書き直す２～さらなる改善を試みる～

# はじめに

これまで下記の記事で 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)

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

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

ボトムアップ型の課題といっても実装によるが，配列の先頭からマージを行う場合，配列の末尾に未結合の要素が残ってしまう。とくに配列の要素数が２のべき乗＋１の場合，末端の要素がマージされるのは最後になる。最後にマージする二つの区間の要素数がバランスを欠いており，後半部の要素数が１つしかない。

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="592" height="320">
<g fill="pink">
<path d="M32 32 h512 v16 h-512">
<path d="M32 80 h256 v16 h-256">
<path d="M32 128 h128 v16 h-128">
<path d="M288 128 h128 v16 h-128">
<path d="M32 176 h64 v16 h-64">
<path d="M160 176 h64 v16 h-64">
<path d="M288 176 h64 v16 h-64">
<path d="M416 176 h64 v16 h-64">
<path d="M32 224 h32 v16 h-32">
<path d="M96 224 h32 v16 h-32">
<path d="M160 224 h32 v16 h-32">
<path d="M224 224 h32 v16 h-32">
<path d="M288 224 h32 v16 h-32">
<path d="M352 224 h32 v16 h-32">
<path d="M416 224 h32 v16 h-32">
<path d="M480 224 h32 v16 h-32">
<path d="M32 272 h16 v16 h-16">
<path d="M64 272 h16 v16 h-16">
<path d="M96 272 h16 v16 h-16">
<path d="M128 272 h16 v16 h-16">
<path d="M160 272 h16 v16 h-16">
<path d="M192 272 h16 v16 h-16">
<path d="M224 272 h16 v16 h-16">
<path d="M256 272 h16 v16 h-16">
<path d="M288 272 h16 v16 h-16">
<path d="M320 272 h16 v16 h-16">
<path d="M352 272 h16 v16 h-16">
<path d="M384 272 h16 v16 h-16">
<path d="M416 272 h16 v16 h-16">
<path d="M448 272 h16 v16 h-16">
<path d="M480 272 h16 v16 h-16">
<path d="M512 272 h16 v16 h-16">
</g>
<g fill="lightblue">
<path d="M544 32 h16 v16 h-16">
<path d="M288 80 h256 v16 h-256">
<path d="M160 128 h128 v16 h-128">
<path d="M416 128 h128 v16 h-128">
<path d="M96 176 h64 v16 h-64">
<path d="M224 176 h64 v16 h-64">
<path d="M352 176 h64 v16 h-64">
<path d="M480 176 h64 v16 h-64">
<path d="M64 224 h32 v16 h-32">
<path d="M128 224 h32 v16 h-32">
<path d="M192 224 h32 v16 h-32">
<path d="M256 224 h32 v16 h-32">
<path d="M320 224 h32 v16 h-32">
<path d="M384 224 h32 v16 h-32">
<path d="M448 224 h32 v16 h-32">
<path d="M512 224 h32 v16 h-32">
<path d="M48 272 h16 v16 h-16">
<path d="M80 272 h16 v16 h-16">
<path d="M112 272 h16 v16 h-16">
<path d="M144 272 h16 v16 h-16">
<path d="M176 272 h16 v16 h-16">
<path d="M208 272 h16 v16 h-16">
<path d="M240 272 h16 v16 h-16">
<path d="M272 272 h16 v16 h-16">
<path d="M304 272 h16 v16 h-16">
<path d="M336 272 h16 v16 h-16">
<path d="M368 272 h16 v16 h-16">
<path d="M400 272 h16 v16 h-16">
<path d="M432 272 h16 v16 h-16">
<path d="M464 272 h16 v16 h-16">
<path d="M496 272 h16 v16 h-16">
<path d="M528 272 h16 v16 h-16">
</g>
<g fill="black">
<path d="M32 32 h528 v1 h-528">
<path d="M32 48 h528 v1 h-528">
<path d="M32 32 v16 h1 v-16">
<path d="M544 32 v16 h1 v-16">
<path d="M560 32 v16 h1 v-16">
<path d="M32 80 h528 v1 h-528">
<path d="M32 96 h528 v1 h-528">
<path d="M32 80 v16 h1 v-16">
<path d="M288 80 v16 h1 v-16">
<path d="M544 80 v16 h1 v-16">
<path d="M560 80 v16 h1 v-16">
<path d="M32 128 h528 v1 h-528">
<path d="M32 144 h528 v1 h-528">
<path d="M32 128 v16 h1 v-16">
<path d="M160 128 v16 h1 v-16">
<path d="M288 128 v16 h1 v-16">
<path d="M416 128 v16 h1 v-16">
<path d="M544 128 v16 h1 v-16">
<path d="M560 128 v16 h1 v-16">
<path d="M32 176 h528 v1 h-528">
<path d="M32 192 h528 v1 h-528">
<path d="M32 176 v16 h1 v-16">
<path d="M96 176 v16 h1 v-16">
<path d="M160 176 v16 h1 v-16">
<path d="M224 176 v16 h1 v-16">
<path d="M288 176 v16 h1 v-16">
<path d="M352 176 v16 h1 v-16">
<path d="M416 176 v16 h1 v-16">
<path d="M480 176 v16 h1 v-16">
<path d="M544 176 v16 h1 v-16">
<path d="M560 176 v16 h1 v-16">
<path d="M32 224 h528 v1 h-528">
<path d="M32 240 h528 v1 h-528">
<path d="M32 224 v16 h1 v-16">
<path d="M64 224 v16 h1 v-16">
<path d="M96 224 v16 h1 v-16">
<path d="M128 224 v16 h1 v-16">
<path d="M160 224 v16 h1 v-16">
<path d="M192 224 v16 h1 v-16">
<path d="M224 224 v16 h1 v-16">
<path d="M256 224 v16 h1 v-16">
<path d="M288 224 v16 h1 v-16">
<path d="M320 224 v16 h1 v-16">
<path d="M352 224 v16 h1 v-16">
<path d="M384 224 v16 h1 v-16">
<path d="M416 224 v16 h1 v-16">
<path d="M448 224 v16 h1 v-16">
<path d="M480 224 v16 h1 v-16">
<path d="M512 224 v16 h1 v-16">
<path d="M544 224 v16 h1 v-16">
<path d="M560 224 v16 h1 v-16">
<path d="M32 272 h528 v1 h-528">
<path d="M32 288 h528 v1 h-528">
<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="M288 272 v16 h1 v-16">
<path d="M304 272 v16 h1 v-16">
<path d="M320 272 v16 h1 v-16">
<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">
</g>
<g fill="magenta">
<path d="M288 52 l-12 12 h6 v12 h12 v-12 h6">
<path d="M288 100 l-12 12 h6 v12 h12 v-12 h6">
<path d="M288 148 l-12 12 h6 v12 h12 v-12 h6">
<path d="M288 196 l-12 12 h6 v12 h12 v-12 h6">
<path d="M288 244 l-12 12 h6 v12 h12 v-12 h6">
</g>

</svg>
title
<$FIGURE>
図１　配列の要素数が２のべき乗＋１の場合
end title
@enduml
```

ここで GNU C ライブラリの `qsort` では前後二つに分割した配列のうち，後半部の要素数を多くした方が得になることを思い出して欲しい。

> また，配列 `a[]` を前半部と後半部に分割する際，配列の要素数が奇数だと等分割できない。非均等に分割するのであれば，後半部の要素数を多くした方が得だと分かるだろう。これは後半部の要素数のほうが多いと，後半部の要素が残ってしまう確率が高くなるが，その場合，残った要素を転送しなくても済むからだ。実際，配列の要素数 `len` が奇数の場合，前半部の要素数 `n1` よりも後半部の要素数 `n2` がのほうが一つだけ多くなるよう分割される。

前半部の要素数を少なくした方が効率良いのであれば，以下に示すように配列の先頭に未結合の要素を置いたほうが良いだろう。

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="592" height="320">
<g fill="pink">
<path d="M32 32 h16 v16 h-16">
<path d="M48 80 h256 v16 h-256">
<path d="M48 128 h128 v16 h-128">
<path d="M304 128 h128 v16 h-128">
<path d="M48 176 h64 v16 h-64">
<path d="M176 176 h64 v16 h-64">
<path d="M304 176 h64 v16 h-64">
<path d="M432 176 h64 v16 h-64">
<path d="M48 224 h32 v16 h-32">
<path d="M112 224 h32 v16 h-32">
<path d="M175 224 h32 v16 h-32">
<path d="M240 224 h32 v16 h-32">
<path d="M304 224 h32 v16 h-32">
<path d="M368 224 h32 v16 h-32">
<path d="M432 224 h32 v16 h-32">
<path d="M496 224 h32 v16 h-32">
<path d="M48 272 h16 v16 h-16">
<path d="M80 272 h16 v16 h-16">
<path d="M112 272 h16 v16 h-16">
<path d="M144 272 h16 v16 h-16">
<path d="M176 272 h16 v16 h-16">
<path d="M208 272 h16 v16 h-16">
<path d="M240 272 h16 v16 h-16">
<path d="M272 272 h16 v16 h-16">
<path d="M304 272 h16 v16 h-16">
<path d="M336 272 h16 v16 h-16">
<path d="M368 272 h16 v16 h-16">
<path d="M400 272 h16 v16 h-16">
<path d="M432 272 h16 v16 h-16">
<path d="M464 272 h16 v16 h-16">
<path d="M496 272 h16 v16 h-16">
<path d="M528 272 h16 v16 h-16">
</g>
<g fill="lightblue">
<path d="M48 32 h512 v16 h-512">
<path d="M304 80 h256 v16 h-256">
<path d="M176 128 h128 v16 h-128">
<path d="M432 128 h128 v16 h-128">
<path d="M112 176 h64 v16 h-64">
<path d="M240 176 h64 v16 h-64">
<path d="M368 176 h64 v16 h-64">
<path d="M496 176 h64 v16 h-64">
<path d="M80 224 h32 v16 h-32">
<path d="M144 224 h32 v16 h-32">
<path d="M208 224 h32 v16 h-32">
<path d="M272 224 h32 v16 h-32">
<path d="M336 224 h32 v16 h-32">
<path d="M400 224 h32 v16 h-32">
<path d="M464 224 h32 v16 h-32">
<path d="M528 224 h32 v16 h-32">
<path d="M64 272 h16 v16 h-16">
<path d="M96 272 h16 v16 h-16">
<path d="M128 272 h16 v16 h-16">
<path d="M160 272 h16 v16 h-16">
<path d="M192 272 h16 v16 h-16">
<path d="M224 272 h16 v16 h-16">
<path d="M256 272 h16 v16 h-16">
<path d="M288 272 h16 v16 h-16">
<path d="M320 272 h16 v16 h-16">
<path d="M352 272 h16 v16 h-16">
<path d="M384 272 h16 v16 h-16">
<path d="M416 272 h16 v16 h-16">
<path d="M448 272 h16 v16 h-16">
<path d="M480 272 h16 v16 h-16">
<path d="M512 272 h16 v16 h-16">
<path d="M544 272 h16 v16 h-16">
</g>
<g fill="black">
<path d="M32 32 h528 v1 h-528">
<path d="M32 48 h528 v1 h-528">
<path d="M32 32 v16 h1 v-16">
<path d="M48 32 v16 h1 v-16">
<path d="M560 32 v16 h1 v-16">
<path d="M32 80 h528 v1 h-528">
<path d="M32 96 h528 v1 h-528">
<path d="M32 80 v16 h1 v-16">
<path d="M48 80 v16 h1 v-16">
<path d="M304 80 v16 h1 v-16">
<path d="M560 80 v16 h1 v-16">
<path d="M32 128 h528 v1 h-528">
<path d="M32 144 h528 v1 h-528">
<path d="M32 128 v16 h1 v-16">
<path d="M48 128 v16 h1 v-16">
<path d="M176 128 v16 h1 v-16">
<path d="M304 128 v16 h1 v-16">
<path d="M432 128 v16 h1 v-16">
<path d="M560 128 v16 h1 v-16">
<path d="M32 176 h528 v1 h-528">
<path d="M32 192 h528 v1 h-528">
<path d="M32 176 v16 h1 v-16">
<path d="M48 176 v16 h1 v-16">
<path d="M112 176 v16 h1 v-16">
<path d="M176 176 v16 h1 v-16">
<path d="M240 176 v16 h1 v-16">
<path d="M304 176 v16 h1 v-16">
<path d="M368 176 v16 h1 v-16">
<path d="M432 176 v16 h1 v-16">
<path d="M496 176 v16 h1 v-16">
<path d="M560 176 v16 h1 v-16">
<path d="M32 224 h528 v1 h-528">
<path d="M32 240 h528 v1 h-528">
<path d="M32 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="M304 224 v16 h1 v-16">
<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="M32 272 h528 v1 h-528">
<path d="M32 288 h528 v1 h-528">
<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="M288 272 v16 h1 v-16">
<path d="M304 272 v16 h1 v-16">
<path d="M320 272 v16 h1 v-16">
<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">
</g>
<g fill="magenta">
<path d="M288 52 l-12 12 h6 v12 h12 v-12 h6">
<path d="M288 100 l-12 12 h6 v12 h12 v-12 h6">
<path d="M288 148 l-12 12 h6 v12 h12 v-12 h6">
<path d="M288 196 l-12 12 h6 v12 h12 v-12 h6">
<path d="M288 244 l-12 12 h6 v12 h12 v-12 h6">
</g>
</svg>
title
<$FIGURE>
図２　配列の要素数が２のべき乗＋１の場合
end title
@enduml
```

# 改善案

配列の全要素数 $n$，領域の大きさ $s$ とおくと，

- $n \bmod 2s \le s$ のとき，先頭から $n \bmod 2s$ 個の要素は未結合のまま残される。
- $n \bmod 2s > s$ のとき，先頭から $n \bmod 2s$ 個の要素も余さず結合され，前半部が $n \bmod 2s -s$ 個，後半部が $s$ 個となる。

のように場合分けが必要となる。$2s$ で割った余り（剰余演算）を避けるのであれば，初期値 $i = n - 2s$ として $i$ 番目の要素から $s$ 個，$i + s$ 番目の要素から $s$ 個の要素をマージしていき，$i$ は $2s$ ずつ減らしていけばよい。最後の $i \ge 0$ が $n$ を $2s$ で割った余りである。

とりあえずこれをバックワード型と呼ぶことにしよう。

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="592" height="80">
<g fill="pink">
<path d="M48 24 h32 v16 h-32">
<path d="M112 24 h32 v16 h-32">
<path d="M175 24 h32 v16 h-32">
<path d="M240 24 h32 v16 h-32">
<path d="M304 24 h32 v16 h-32">
<path d="M368 24 h32 v16 h-32">
<path d="M432 24 h32 v16 h-32">
<path d="M496 24 h32 v16 h-32">
</g>
<g fill="lightblue">
<path d="M80 24 h32 v16 h-32">
<path d="M144 24 h32 v16 h-32">
<path d="M208 24 h32 v16 h-32">
<path d="M272 24 h32 v16 h-32">
<path d="M336 24 h32 v16 h-32">
<path d="M400 24 h32 v16 h-32">
<path d="M464 24 h32 v16 h-32">
<path d="M528 24 h32 v16 h-32">
</g>
<g fill="black">
<path d="M32 24 h528 v1 h-528">
<path d="M32 40 h528 v1 h-528">
<path d="M32 24 v16 h1 v-16">
<path d="M48 24 v16 h1 v-16">
<path d="M80 24 v16 h1 v-16">
<path d="M112 24 v16 h1 v-16">
<path d="M144 24 v16 h1 v-16">
<path d="M176 24 v16 h1 v-16">
<path d="M208 24 v16 h1 v-16">
<path d="M240 24 v16 h1 v-16">
<path d="M272 24 v16 h1 v-16">
<path d="M304 24 v16 h1 v-16">
<path d="M336 24 v16 h1 v-16">
<path d="M368 24 v16 h1 v-16">
<path d="M400 24 v16 h1 v-16">
<path d="M432 24 v16 h1 v-16">
<path d="M464 24 v16 h1 v-16">
<path d="M496 24 v16 h1 v-16">
<path d="M528 24 v16 h1 v-16">
<path d="M560 24 v16 h1 v-16">
</g>
<g fill="magenta">
<path d="M495 48 v16 h2 v-16">
<path d="M496 57 h-64 v4 l-16 -5 l16 -5 v4 h64">
</g>
</svg>
title
<$FIGURE>
図３　バックワード型
end title
@enduml
```

しかし，領域の大きさ $s$ は２のべき乗数なので，$2s$ で割った余りを求める剰余演算は単に $2s - 1$ との論理積（AND）を求めるだけでよい。したがって $i = n \bmod 2s$ として，$i$ を $2s$ ずつ増やしていく方法も考えられる。これをフォワード型と呼ぶことにする。


```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="592" height="80">
<g fill="pink">
<path d="M48 24 h32 v16 h-32">
<path d="M112 24 h32 v16 h-32">
<path d="M175 24 h32 v16 h-32">
<path d="M240 24 h32 v16 h-32">
<path d="M304 24 h32 v16 h-32">
<path d="M368 24 h32 v16 h-32">
<path d="M432 24 h32 v16 h-32">
<path d="M496 24 h32 v16 h-32">
</g>
<g fill="lightblue">
<path d="M80 24 h32 v16 h-32">
<path d="M144 24 h32 v16 h-32">
<path d="M208 24 h32 v16 h-32">
<path d="M272 24 h32 v16 h-32">
<path d="M336 24 h32 v16 h-32">
<path d="M400 24 h32 v16 h-32">
<path d="M464 24 h32 v16 h-32">
<path d="M528 24 h32 v16 h-32">
</g>
<g fill="black">
<path d="M32 24 h528 v1 h-528">
<path d="M32 40 h528 v1 h-528">
<path d="M32 24 v16 h1 v-16">
<path d="M48 24 v16 h1 v-16">
<path d="M80 24 v16 h1 v-16">
<path d="M112 24 v16 h1 v-16">
<path d="M144 24 v16 h1 v-16">
<path d="M176 24 v16 h1 v-16">
<path d="M208 24 v16 h1 v-16">
<path d="M240 24 v16 h1 v-16">
<path d="M272 24 v16 h1 v-16">
<path d="M304 24 v16 h1 v-16">
<path d="M336 24 v16 h1 v-16">
<path d="M368 24 v16 h1 v-16">
<path d="M400 24 v16 h1 v-16">
<path d="M432 24 v16 h1 v-16">
<path d="M464 24 v16 h1 v-16">
<path d="M496 24 v16 h1 v-16">
<path d="M528 24 v16 h1 v-16">
<path d="M560 24 v16 h1 v-16">
</g>
<g fill="magenta">
<path d="M47 48 v16 h2 v-16">
<path d="M48 57 h64 v4 l16 -5 l-16 -5 v4 h-64">
</g>
</svg>
title
<$FIGURE>
図４　フォワード型
end title
@enduml
```

なぜ，いきなりバックワード型とフォワード型の二種類を作成したのかというと，まず最初にバックワード型を作ったとき，なんとなくキャッシュメモリのヒット率が悪くなるような予感がしたからだ。

一般にメモリアクセス，とくにリード（読出し）動作はランダクアクセスよりもシーケンシャルアクセスのほうが高速だが，それはキャッシュメモリにヒットする確率が高くなるからだ。ただし，シーケンシャルアクセスといっても参照方向が正順と逆順で大差ないのか，あるいは差が生じるのかについては興味深いテーマであろう。
※筆者はフォワード型のほうが速いと思っている。

# 実装コード

実装コードを以下に示す。

<details><summary><b>ボトムアップ型マージソート関数その２（バックワード型）</b></summary>

```c++:ボトムアップ型マージソート関数その２
/* 001 */ #include <stdlib.h>
/* 002 */ typedef int     (*COMPARE)(int, int);
/* 003 */ #define TEMP_SIZE   256
/* 004 */ static  void    swap(int *p, int *q) {
/* 005 */     int temp = *p;
/* 006 */     *p = *q;
/* 007 */     *q = temp;
/* 008 */ }
/* 009 */ static  void    merge(int *buf, int *a, int n1, int n2, COMPARE compare) {
/* 010 */     int n = n1 + n2;
/* 011 */     int *p1 = a;
/* 012 */     int *p2 = a + n1;
/* 013 */     int *q = buf;
/* 014 */     for(;;) {
/* 015 */         if(compare(*p1, *p2) <= 0) {
/* 016 */             *q++ = *p1++; if(--n1 == 0) break;
/* 017 */         } else {
/* 018 */             *q++ = *p2++; if(--n2 == 0) break;
/* 019 */         }
/* 020 */     }
/* 021 */     while(n1 > 0) {
/* 022 */         *q++ = *p1++; n1--;
/* 023 */     }
/* 024 */     for(int i = 0; i < n - n2; i++)
/* 025 */         a[i] = buf[i];
/* 026 */ }
/* 027 */ static  void    sort(int *buf, int *a, int len, COMPARE compare) {
/* 028 */     for(int i = len - 2; i >= 0; i -= 2)
/* 029 */         if(compare(a[i], a[i + 1]) > 0) swap(&a[i], &a[i + 1]);
/* 030 */     for(int s = 2; s < len; s = s * 2) {
/* 031 */         int i, adj;
/* 032 */         for(i = len - s * 2; i >= 0; i -= s * 2)
/* 033 */             merge(buf, &a[i], s, s, compare);
/* 034 */         if((adj = i + s) > 0)
/* 035 */             merge(buf, a, adj, s, compare);
/* 036 */     }
/* 037 */ }
/* 038 */ void    msort2(int *a, int len, COMPARE compare) {
/* 039 */     if(len < 2) return;
/* 040 */     if(len <= TEMP_SIZE) {
/* 041 */         int tmp[TEMP_SIZE];
/* 042 */         sort(tmp, a, len, compare);
/* 043 */     } else {
/* 044 */         int *buf = (int*)malloc(sizeof(int) * len);
/* 045 */         if(buf == (int*)NULL) return;
/* 046 */         sort(buf, a, len, compare);
/* 047 */         free(buf);
/* 048 */     }
/* 049 */ }
```

</details>

<details><summary><b>ボトムアップ型マージソート関数その３（フォワード型）</b></summary>

```c++:ボトムアップ型マージソート関数その３
/* 001 */ #include <stdlib.h>
/* 002 */ typedef int     (*COMPARE)(int, int);
/* 003 */ #define TEMP_SIZE   256
/* 004 */ static  void    swap(int *p, int *q) {
/* 005 */     int temp = *p;
/* 006 */     *p = *q;
/* 007 */     *q = temp;
/* 008 */ }
/* 009 */ static  void    merge(int *buf, int *a, int n1, int n2, COMPARE compare) {
/* 010 */     int n = n1 + n2;
/* 011 */     int *p1 = a;
/* 012 */     int *p2 = a + n1;
/* 013 */     int *q = buf;
/* 014 */     for(;;) {
/* 015 */         if(compare(*p1, *p2) <= 0) {
/* 016 */             *q++ = *p1++; if(--n1 == 0) break;
/* 017 */         } else {
/* 018 */             *q++ = *p2++; if(--n2 == 0) break;
/* 019 */         }
/* 020 */     }
/* 021 */     while(n1 > 0) {
/* 022 */         *q++ = *p1++; n1--;
/* 023 */     }
/* 024 */     for(int i = 0; i < n - n2; i++)
/* 025 */         a[i] = buf[i];
/* 026 */ }
/* 027 */ static  void    sort(int *buf, int *a, int len, COMPARE compare) {
/* 028 */     for(int i = len & 1; i + 1 < len; i += 2)
/* 029 */         if(compare(a[i], a[i + 1]) > 0) swap(&a[i], &a[i + 1]);
/* 030 */     for(int s = 2; s < len; s = s * 2) {
/* 031 */         int i = len & (s * 2 - 1);
/* 032 */         int adj;
/* 033 */         if((adj = i - s) > 0)
/* 034 */             merge(buf, a, adj, s, compare);
/* 035 */         for(; i + s < len; i += s * 2)
/* 036 */             merge(buf, &a[i], s, s, compare);
/* 037 */     }
/* 038 */ }
/* 039 */ void    msort3(int *a, int len, COMPARE compare) {
/* 040 */     if(len < 2) return;
/* 041 */     if(len <= TEMP_SIZE) {
/* 042 */         int tmp[TEMP_SIZE];
/* 043 */         sort(tmp, a, len, compare);
/* 044 */     } else {
/* 045 */         int *buf = (int*)malloc(sizeof(int) * len);
/* 046 */         if(buf == (int*)NULL) return;
/* 047 */         sort(buf, a, len, compare);
/* 048 */         free(buf);
/* 049 */     }
/* 050 */ }
```

</details>

# 試験条件

- 要素数 200,000,000 個のint 型の配列の昇順ソートを行う。マージソートの場合，同サイズの配列がもう一つ必要になることから，32bit プログラムではほぼ上限値である。
4×200,000,000 bytes = 0x2FAF0800 bytes
- データの順序は以下の四種類とする。
  - ゼロ
  - 昇順：0 → 199,999,999
  - 降順：199,999,999 → 0
  - 乱数：0～199,999,999 の範囲の一様乱数，乱数発生器は XorShift とした3
- 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
- 評価するソート関数を以下に示す。
  - uCRT：クイックソート，uCRT 版 `qsort` の意訳版
  - 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">uCRT</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=7>Visual C++<br>32bit版</th>
    <th>ゼロ</th>
    <td style="text-align:right">0.090</td>
    <td style="text-align:right">2.660</td>
    <td style="text-align:right">2.835</td>
    <td style="text-align:right">2.841</td>
    <td style="text-align:right">2.264</td></tr>
<tr></tr>
<tr><th>昇順</th>
    <td style="text-align:right">1.433</td>
    <td style="text-align:right">2.656</td>
    <td style="text-align:right">2.848</td>
    <td style="text-align:right">2.851</td>
    <td style="text-align:right">2.267</td></tr>
<tr></tr>
<tr><th>降順</th>
    <td style="text-align:right">1.475</td>
    <td style="text-align:right">3.914</td>
    <td style="text-align:right">4.668</td>
    <td style="text-align:right">4.862</td>
    <td style="text-align:right">3.829</td></tr>
<tr></tr>
<tr><th>乱数</th>
    <td style="text-align:right">15.505</td>
    <td style="text-align:right">17.996</td>
    <td style="text-align:right">19.431</td>
    <td style="text-align:right">19.789</td>
    <td style="text-align:right">17.524</td></tr>
<tr></tr>
<tr><th rowspan=7>Visual C++<br>64bit版</th>
    <th>ゼロ</th>
    <td style="text-align:right">0.093</td>
    <td style="text-align:right">2.470</td>
    <td style="text-align:right">2.158</td>
    <td style="text-align:right">2.123</td>
    <td style="text-align:right">2.086</td></tr>
<tr></tr>
<tr><th>昇順</th>
    <td style="text-align:right">1.582</td>
    <td style="text-align:right">2.473</td>
    <td style="text-align:right">2.148</td>
    <td style="text-align:right">2.126</td>
    <td style="text-align:right">2.087</td></tr>
<tr></tr>
<tr><th>降順</th>
    <td style="text-align:right">1.617</td>
    <td style="text-align:right">3.769</td>
    <td style="text-align:right">3.370</td>
    <td style="text-align:right">3.517</td>
    <td style="text-align:right">3.432</td></tr>
<tr></tr>
<tr><th>乱数</th>
    <td style="text-align:right">15.500</td>
    <td style="text-align:right">21.129</td>
    <td style="text-align:right">20.050</td>
    <td style="text-align:right">20.192</td>
    <td style="text-align:right">20.114</td></tr>
<tr></tr>
<tr><th rowspan=7>LLVM clang-cl<br>32bit版</th>
    <th>ゼロ</th>
    <td style="text-align:right">0.098</td>
    <td style="text-align:right">2.066</td>
    <td style="text-align:right">2.095</td>
    <td style="text-align:right">2.018</td>
    <td style="text-align:right">1.963</td></tr>
<tr></tr>
<tr><th>昇順</th>
    <td style="text-align:right">1.627</td>
    <td style="text-align:right">2.060</td>
    <td style="text-align:right">2.109</td>
    <td style="text-align:right">2.049</td>
    <td style="text-align:right">1.974</td></tr>
<tr></tr>
<tr><th>降順</th>
    <td style="text-align:right">1.688</td>
    <td style="text-align:right">3.642</td>
    <td style="text-align:right">3.015</td>
    <td style="text-align:right">3.278</td>
    <td style="text-align:right">3.063</td></tr>
<tr></tr>
<tr><th>乱数</th>
    <td style="text-align:right">15.636</td>
    <td style="text-align:right">16.487</td>
    <td style="text-align:right">15.981</td>
    <td style="text-align:right">16.199</td>
    <td style="text-align:right">15.876</td></tr>
<tr></tr>
<tr><th rowspan=7>LLVM clang-cl<br>64bit版</th>
    <th>ゼロ</th>
    <td style="text-align:right">0.089</td>
    <td style="text-align:right">1.958</td>
    <td style="text-align:right">1.679</td>
    <td style="text-align:right">1.547</td>
    <td style="text-align:right">1.492</td></tr>
<tr></tr>
<tr><th>昇順</th>
    <td style="text-align:right">1.460</td>
    <td style="text-align:right">1.997</td>
    <td style="text-align:right">1.663</td>
    <td style="text-align:right">1.563</td>
    <td style="text-align:right">1.488</td></tr>
<tr></tr>
<tr><th>降順</th>
    <td style="text-align:right">1.523</td>
    <td style="text-align:right">2.942</td>
    <td style="text-align:right">2.456</td>
    <td style="text-align:right">2.626</td>
    <td style="text-align:right">2.512</td></tr>
<tr></tr>
<tr><th>乱数</th>
    <td style="text-align:right">15.710</td>
    <td style="text-align:right">16.022</td>
    <td style="text-align:right">15.853</td>
    <td style="text-align:right">15.922</td>
    <td style="text-align:right">15.539</td></tr>
<tr></tr>
<tr><th rowspan=7>intel icx-cl<br>32bit版</th>
    <th>ゼロ</th>
    <td style="text-align:right">0.070</td>
    <td style="text-align:right">2.488</td>
    <td style="text-align:right">2.038</td>
    <td style="text-align:right">1.979</td>
    <td style="text-align:right">1.945</td></tr>
<tr></tr>
<tr><th>昇順</th>
    <td style="text-align:right">1.592</td>
    <td style="text-align:right">2.498</td>
    <td style="text-align:right">2.050</td>
    <td style="text-align:right">1.989</td>
    <td style="text-align:right">1.954</td></tr>
<tr></tr>
<tr><th>降順</th>
    <td style="text-align:right">1.691</td>
    <td style="text-align:right">3.333</td>
    <td style="text-align:right">2.877</td>
    <td style="text-align:right">2.964</td>
    <td style="text-align:right">2.871</td></tr>
<tr></tr>
<tr><th>乱数</th>
    <td style="text-align:right">17.120</td>
    <td style="text-align:right">17.809</td>
    <td style="text-align:right">17.767</td>
    <td style="text-align:right">17.107</td>
    <td style="text-align:right">17.582</td></tr>
<tr></tr>
<tr><th rowspan=7>intel icx-cl<br>32bit版</th>
    <th>ゼロ</th>
    <td style="text-align:right">0.064</td>
    <td style="text-align:right">1.811</td>
    <td style="text-align:right">1.621</td>
    <td style="text-align:right">1.582</td>
    <td style="text-align:right">1.542</td></tr>
<tr></tr>
<tr><th>昇順</th>
    <td style="text-align:right">1.366</td>
    <td style="text-align:right">1.797</td>
    <td style="text-align:right">1.608</td>
    <td style="text-align:right">1.583</td>
    <td style="text-align:right">1.550</td></tr>
<tr></tr>
<tr><th>降順</th>
    <td style="text-align:right">1.491</td>
    <td style="text-align:right">2.507</td>
    <td style="text-align:right">2.418</td>
    <td style="text-align:right">2.526</td>
    <td style="text-align:right">2.428</td></tr>
<tr></tr>
<tr><th>乱数</th>
    <td style="text-align:right">16.584</td>
    <td style="text-align:right">15.969</td>
    <td style="text-align:right">15.682</td>
    <td style="text-align:right">15.497</td>
    <td style="text-align:right">15.673</td></tr>
</tbody>
</table>

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

<font color=#5B9BD5>■</font>uCRT，<font color=#ED7D31>■</font>glibc，<font color=#A5A5A5>■</font>merge，<font color=#FFC000>■</font>merge2，<font color=#4472C4>■</font>merge3

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="320" height="360">
<g fill="lightgray">
<path d="M30 330 h280 v1 h-280">
<path d="M30 270 h280 v1 h-280">
<path d="M30 210 h280 v1 h-280">
<path d="M30 150 h280 v1 h-280">
<path d="M30 90 h280 v1 h-280">
<path d="M30 30 h280 v1 h-280">
</g>
<text x="15" y="336" font-size="16" fill="black">0</text>
<text x="15" y="276" font-size="16" fill="black">5</text>
<text x="5" y="216" font-size="16" fill="black">10</text>
<text x="5" y="156" font-size="16" fill="black">15</text>
<text x="5" y="96" font-size="16" fill="black">20</text>
<text x="5" y="36" font-size="16" fill="black">25</text>
<text x="48" y="350" font-size="16" fill="black">ゼロ</text>
<text x="118" y="350" font-size="16" fill="black">昇順</text>
<text x="188" y="350" font-size="16" fill="black">降順</text>
<text x="258" y="350" font-size="16" fill="black">乱数</text>
<g fill="#5B9BD5">
<path d="M43 330 h8 v-1 h-8">
<path d="M113 330 h8 v-17 h-8">
<path d="M183 330 h8 v-18 h-8">
<path d="M253 330 h8 v-186 h-8">
</g>
<g fill="#ED7D31">
<path d="M52 330 h8 v-32 h-8">
<path d="M122 330 h8 v-32 h-8">
<path d="M192 330 h8 v-47 h-8">
<path d="M262 330 h8 v-216 h-8">
</g>
<g fill="#A5A5A5">
<path d="M61 330 h8 v-34 h-8">
<path d="M131 330 h8 v-34 h-8">
<path d="M201 330 h8 v-56 h-8">
<path d="M271 330 h8 v-233 h-8">
</g>
<g fill="#FFC000">
<path d="M70 330 h8 v-34 h-8">
<path d="M140 330 h8 v-34 h-8">
<path d="M210 330 h8 v-58 h-8">
<path d="M280 330 h8 v-237 h-8">
</g>
<g fill="#4472C4">
<path d="M79 330 h8 v-27 h-8">
<path d="M149 330 h8 v-27 h-8">
<path d="M219 330 h8 v-46 h-8">
<path d="M289 330 h8 v-210 h-8">
</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="320" height="360">
<g fill="lightgray">
<path d="M30 330 h280 v1 h-280">
<path d="M30 270 h280 v1 h-280">
<path d="M30 210 h280 v1 h-280">
<path d="M30 150 h280 v1 h-280">
<path d="M30 90 h280 v1 h-280">
<path d="M30 30 h280 v1 h-280">
</g>
<text x="15" y="336" font-size="16" fill="black">0</text>
<text x="15" y="276" font-size="16" fill="black">5</text>
<text x="5" y="216" font-size="16" fill="black">10</text>
<text x="5" y="156" font-size="16" fill="black">15</text>
<text x="5" y="96" font-size="16" fill="black">20</text>
<text x="5" y="36" font-size="16" fill="black">25</text>
<text x="48" y="350" font-size="16" fill="black">ゼロ</text>
<text x="118" y="350" font-size="16" fill="black">昇順</text>
<text x="188" y="350" font-size="16" fill="black">降順</text>
<text x="258" y="350" font-size="16" fill="black">乱数</text>
<g fill="#5B9BD5">
<path d="M43 330 h8 v-1 h-8">
<path d="M113 330 h8 v-19 h-8">
<path d="M183 330 h8 v-19 h-8">
<path d="M253 330 h8 v-186 h-8">
</g>
<g fill="#ED7D31">
<path d="M52 330 h8 v-30 h-8">
<path d="M122 330 h8 v-30 h-8">
<path d="M192 330 h8 v-45 h-8">
<path d="M262 330 h8 v-254 h-8">
</g>
<g fill="#A5A5A5">
<path d="M61 330 h8 v-26 h-8">
<path d="M131 330 h8 v-26 h-8">
<path d="M201 330 h8 v-40 h-8">
<path d="M271 330 h8 v-241 h-8">
</g>
<g fill="#FFC000">
<path d="M70 330 h8 v-25 h-8">
<path d="M140 330 h8 v-26 h-8">
<path d="M210 330 h8 v-42 h-8">
<path d="M280 330 h8 v-242 h-8">
</g>
<g fill="#4472C4">
<path d="M79 330 h8 v-25 h-8">
<path d="M149 330 h8 v-25 h-8">
<path d="M219 330 h8 v-41 h-8">
<path d="M289 330 h8 v-241 h-8">
</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="320" height="360">
<g fill="lightgray">
<path d="M30 330 h280 v1 h-280">
<path d="M30 270 h280 v1 h-280">
<path d="M30 210 h280 v1 h-280">
<path d="M30 150 h280 v1 h-280">
<path d="M30 90 h280 v1 h-280">
<path d="M30 30 h280 v1 h-280">
</g>
<text x="15" y="336" font-size="16" fill="black">0</text>
<text x="15" y="276" font-size="16" fill="black">5</text>
<text x="5" y="216" font-size="16" fill="black">10</text>
<text x="5" y="156" font-size="16" fill="black">15</text>
<text x="5" y="96" font-size="16" fill="black">20</text>
<text x="5" y="36" font-size="16" fill="black">25</text>
<text x="48" y="350" font-size="16" fill="black">ゼロ</text>
<text x="118" y="350" font-size="16" fill="black">昇順</text>
<text x="188" y="350" font-size="16" fill="black">降順</text>
<text x="258" y="350" font-size="16" fill="black">乱数</text>
<g fill="#5B9BD5">
<path d="M43 330 h8 v-1 h-8">
<path d="M113 330 h8 v-20 h-8">
<path d="M183 330 h8 v-20 h-8">
<path d="M253 330 h8 v-188 h-8">
</g>
<g fill="#ED7D31">
<path d="M52 330 h8 v-25 h-8">
<path d="M122 330 h8 v-25 h-8">
<path d="M192 330 h8 v-44 h-8">
<path d="M262 330 h8 v-198 h-8">
</g>
<g fill="#A5A5A5">
<path d="M61 330 h8 v-25 h-8">
<path d="M131 330 h8 v-25 h-8">
<path d="M201 330 h8 v-36 h-8">
<path d="M271 330 h8 v-192 h-8">
</g>
<g fill="#FFC000">
<path d="M70 330 h8 v-24 h-8">
<path d="M140 330 h8 v-25 h-8">
<path d="M210 330 h8 v-39 h-8">
<path d="M280 330 h8 v-194 h-8">
</g>
<g fill="#4472C4">
<path d="M79 330 h8 v-24 h-8">
<path d="M149 330 h8 v-24 h-8">
<path d="M219 330 h8 v-37 h-8">
<path d="M289 330 h8 v-191 h-8">
</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="320" height="360">
<g fill="lightgray">
<path d="M30 330 h280 v1 h-280">
<path d="M30 270 h280 v1 h-280">
<path d="M30 210 h280 v1 h-280">
<path d="M30 150 h280 v1 h-280">
<path d="M30 90 h280 v1 h-280">
<path d="M30 30 h280 v1 h-280">
</g>
<text x="15" y="336" font-size="16" fill="black">0</text>
<text x="15" y="276" font-size="16" fill="black">5</text>
<text x="5" y="216" font-size="16" fill="black">10</text>
<text x="5" y="156" font-size="16" fill="black">15</text>
<text x="5" y="96" font-size="16" fill="black">20</text>
<text x="5" y="36" font-size="16" fill="black">25</text>
<text x="48" y="350" font-size="16" fill="black">ゼロ</text>
<text x="118" y="350" font-size="16" fill="black">昇順</text>
<text x="188" y="350" font-size="16" fill="black">降順</text>
<text x="258" y="350" font-size="16" fill="black">乱数</text>
<g fill="#5B9BD5">
<path d="M43 330 h8 v-1 h-8">
<path d="M113 330 h8 v-18 h-8">
<path d="M183 330 h8 v-18 h-8">
<path d="M253 330 h8 v-189 h-8">
</g>
<g fill="#ED7D31">
<path d="M52 330 h8 v-23 h-8">
<path d="M122 330 h8 v-24 h-8">
<path d="M192 330 h8 v-35 h-8">
<path d="M262 330 h8 v-192 h-8">
</g>
<g fill="#A5A5A5">
<path d="M61 330 h8 v-20 h-8">
<path d="M131 330 h8 v-20 h-8">
<path d="M201 330 h8 v-29 h-8">
<path d="M271 330 h8 v-190 h-8">
</g>
<g fill="#FFC000">
<path d="M70 330 h8 v-19 h-8">
<path d="M140 330 h8 v-19 h-8">
<path d="M210 330 h8 v-32 h-8">
<path d="M280 330 h8 v-191 h-8">
</g>
<g fill="#4472C4">
<path d="M79 330 h8 v-18 h-8">
<path d="M149 330 h8 v-18 h-8">
<path d="M219 330 h8 v-30 h-8">
<path d="M289 330 h8 v-186 h-8">
</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="320" height="360">
<g fill="lightgray">
<path d="M30 330 h280 v1 h-280">
<path d="M30 270 h280 v1 h-280">
<path d="M30 210 h280 v1 h-280">
<path d="M30 150 h280 v1 h-280">
<path d="M30 90 h280 v1 h-280">
<path d="M30 30 h280 v1 h-280">
</g>
<text x="15" y="336" font-size="16" fill="black">0</text>
<text x="15" y="276" font-size="16" fill="black">5</text>
<text x="5" y="216" font-size="16" fill="black">10</text>
<text x="5" y="156" font-size="16" fill="black">15</text>
<text x="5" y="96" font-size="16" fill="black">20</text>
<text x="5" y="36" font-size="16" fill="black">25</text>
<text x="48" y="350" font-size="16" fill="black">ゼロ</text>
<text x="118" y="350" font-size="16" fill="black">昇順</text>
<text x="188" y="350" font-size="16" fill="black">降順</text>
<text x="258" y="350" font-size="16" fill="black">乱数</text>
<g fill="#5B9BD5">
<path d="M43 330 h8 v-1 h-8">
<path d="M113 330 h8 v-19 h-8">
<path d="M183 330 h8 v-20 h-8">
<path d="M253 330 h8 v-205 h-8">
</g>
<g fill="#ED7D31">
<path d="M52 330 h8 v-30 h-8">
<path d="M122 330 h8 v-30 h-8">
<path d="M192 330 h8 v-40 h-8">
<path d="M262 330 h8 v-214 h-8">
</g>
<g fill="#A5A5A5">
<path d="M61 330 h8 v-24 h-8">
<path d="M131 330 h8 v-25 h-8">
<path d="M201 330 h8 v-35 h-8">
<path d="M271 330 h8 v-213 h-8">
</g>
<g fill="#FFC000">
<path d="M70 330 h8 v-24 h-8">
<path d="M140 330 h8 v-24 h-8">
<path d="M210 330 h8 v-36 h-8">
<path d="M280 330 h8 v-205 h-8">
</g>
<g fill="#4472C4">
<path d="M79 330 h8 v-23 h-8">
<path d="M149 330 h8 v-23 h-8">
<path d="M219 330 h8 v-34 h-8">
<path d="M289 330 h8 v-211 h-8">
</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="320" height="360">
<g fill="lightgray">
<path d="M30 330 h280 v1 h-280">
<path d="M30 270 h280 v1 h-280">
<path d="M30 210 h280 v1 h-280">
<path d="M30 150 h280 v1 h-280">
<path d="M30 90 h280 v1 h-280">
<path d="M30 30 h280 v1 h-280">
</g>
<text x="15" y="336" font-size="16" fill="black">0</text>
<text x="15" y="276" font-size="16" fill="black">5</text>
<text x="5" y="216" font-size="16" fill="black">10</text>
<text x="5" y="156" font-size="16" fill="black">15</text>
<text x="5" y="96" font-size="16" fill="black">20</text>
<text x="5" y="36" font-size="16" fill="black">25</text>
<text x="48" y="350" font-size="16" fill="black">ゼロ</text>
<text x="118" y="350" font-size="16" fill="black">昇順</text>
<text x="188" y="350" font-size="16" fill="black">降順</text>
<text x="258" y="350" font-size="16" fill="black">乱数</text>
<g fill="#5B9BD5">
<path d="M43 330 h8 v-1 h-8">
<path d="M113 330 h8 v-16 h-8">
<path d="M183 330 h8 v-18 h-8">
<path d="M253 330 h8 v-199 h-8">
</g>
<g fill="#ED7D31">
<path d="M52 330 h8 v-22 h-8">
<path d="M122 330 h8 v-22 h-8">
<path d="M192 330 h8 v-30 h-8">
<path d="M262 330 h8 v-192 h-8">
</g>
<g fill="#A5A5A5">
<path d="M61 330 h8 v-19 h-8">
<path d="M131 330 h8 v-19 h-8">
<path d="M201 330 h8 v-29 h-8">
<path d="M271 330 h8 v-188 h-8">
</g>
<g fill="#FFC000">
<path d="M70 330 h8 v-19 h-8">
<path d="M140 330 h8 v-19 h-8">
<path d="M210 330 h8 v-30 h-8">
<path d="M280 330 h8 v-186 h-8">
</g>
<g fill="#4472C4">
<path d="M79 330 h8 v-19 h-8">
<path d="M149 330 h8 v-19 h-8">
<path d="M219 330 h8 v-29 h-8">
<path d="M289 330 h8 v-188 h-8">
</g>
</svg>
title
<$FIGURE>
図６　intel icx-cl 64bit（単位は秒）
end title
@enduml
```

# 結論

あれこれ工夫しても大して変わらんな・・・

# 次回

次回に続く。

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