マージソートを非再帰型に書き直す～誰でも思いつくアイディアだが～

# はじめに

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

- [GNU C Libraryのqsortはクイックソートではないの？ - Qiita](https://qiita.com/TETSURO1999/items/3eff3b6a5e3983630f3c)
- [最強コンパイラを使えばマージソートは遅くない - Qiita](https://qiita.com/TETSURO1999/items/0cc093f427531407d2d4)

LLVM clang や intel C++ コンパイラなど最強コンパイラを使えばマージソートはクイックソートに肉薄できることが分かったが，そもそもクイックソートのほうがもともとベースとなったコードに細かい工夫が施されていたので公平な比較では無かったと思う。

> - `qsort_glibc()` は普通に再帰関数として作成しているが，`qsort_ucrt()` は再帰関数ではなくループ処理で済ませており，再帰関数の呼び出しオーバーヘッドを減らすなど細かい工夫が施されている。
>
> - `qsort_glibc()` は配列の要素数が 2 個になってもマージソートを行っているが，`qsort_ucrt()` は分割された配列の要素数が 8 個以下になると選択ソートに切り替えるなど細かい工夫が施されている。

ということで本記事ではマージソートの改善に取り組みたい。

# 基本的なアイディア

再帰型のマージソートでは対象となる配列を二つに分割してソートを実行し，二つのソート結果を比較しながら結合（マージ）する。例外事項も少なく，コードはコンパクトに収まり綺麗に書ける。ただし，配列の要素数が一つになるまで分割を繰り返してから結合が始まるので，関数呼び出しのオーバーヘッドが気になるところではある。

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="512" height="288">
<g fill="cyan">
<path d="M141  52 v12 h-3 l6 12 l6 -12 h-3 v-12">
<path d="M365  52 v12 h-3 l6 12 l6 -12 h-3 v-12">
<path d="M85  100 v12 h-3 l6 12 l6 -12 h-3 v-12">
<path d="M197 100 v12 h-3 l6 12 l6 -12 h-3 v-12">
<path d="M309 100 v12 h-3 l6 12 l6 -12 h-3 v-12">
<path d="M421 100 v12 h-3 l6 12 l6 -12 h-3 v-12">
<path d="M54  148 v12 h-3 l6 12 l6 -12 h-3 v-12">
<path d="M113 148 v12 h-3 l6 12 l6 -12 h-3 v-12">
<path d="M169 148 v12 h-3 l6 12 l6 -12 h-3 v-12">
<path d="M227 148 v12 h-3 l6 12 l6 -12 h-3 v-12">
<path d="M281 148 v12 h-3 l6 12 l6 -12 h-3 v-12">
<path d="M337 148 v12 h-3 l6 12 l6 -12 h-3 v-12">
<path d="M393 148 v12 h-3 l6 12 l6 -12 h-3 v-12">
<path d="M449 148 v12 h-3 l6 12 l6 -12 h-3 v-12">
<path d="M43  196 v12 h-3 l6 12 l6 -12 h-3 v-12">
<path d="M71  196 v12 h-3 l6 12 l6 -12 h-3 v-12">
<path d="M36  244 v12 h-3 l6 12 l6 -12 h-3 v-12">
<path d="M50  244 v12 h-3 l6 12 l6 -12 h-3 v-12">
<path d="M64  244 v12 h-3 l6 12 l6 -12 h-3 v-12">
<path d="M78  244 v12 h-3 l6 12 l6 -12 h-3 v-12">
</g>
<g fill="black">
<path d="M32   32 v16 h1 v-16">
<path d="M480  32 v16 h1 v-16">
<path d="M32   32 h448 v1 h-448">
<path d="M32   48 h448 v1 h-448">
<path d="M32   80 v16 h1 v-16">
<path d="M256  80 v16 h1 v-16">
<path d="M480  80 v16 h1 v-16">
<path d="M32   80 h448 v1 h-448">
<path d="M32   96 h448 v1 h-448">
<path d="M32  128 v16 h1 v-16">
<path d="M144 128 v16 h1 v-16">
<path d="M256 128 v16 h1 v-16">
<path d="M368 128 v16 h1 v-16">
<path d="M480 128 v16 h1 v-16">
<path d="M32  128 h448 v1 h-448">
<path d="M32  144 h448 v1 h-448">
<path d="M32  176 v16 h1 v-16">
<path d="M88  176 v16 h1 v-16">
<path d="M144 176 v16 h1 v-16">
<path d="M200 176 v16 h1 v-16">
<path d="M256 176 v16 h1 v-16">
<path d="M312 176 v16 h1 v-16">
<path d="M368 176 v16 h1 v-16">
<path d="M424 176 v16 h1 v-16">
<path d="M480 176 v16 h1 v-16">
<path d="M32  176 h448 v1 h-448">
<path d="M32  192 h448 v1 h-448">
<path d="M32  224 v16 h1 v-16">
<path d="M60  224 v16 h1 v-16">
<path d="M88  224 v16 h1 v-16">
<path d="M480 224 v16 h1 v-16">
<path d="M32  224 h448 v1 h-448">
<path d="M32  240 h448 v1 h-448">
</g>
</svg>
title
<$FIGURE>
図１　トップダウン型
end title
@enduml
```

一方，非再帰型のマージソートはいきなり結合から始まる。隣接する要素を結合していくたびに結合サイズが倍々ゲームで大きくなり，最後一つになれば終了である。非再帰型のマージソートは誰でも思いつくアイディアのようで先行研究は多い[^1][^2][^3]。非再帰型のマージソートをボトムアップ型と名付けようと思ったら，既にそのような名称で呼ばれているようだ。

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="512" height="288">
<g fill="magenta">
<path d="M144   4 l-6 12 h3 v12 h6 v-12 h3">
<path d="M368   4 l-6 12 h3 v12 h6 v-12 h3">
<path d="M88   52 l-6 12 h3 v12 h6 v-12 h3">
<path d="M200  52 l-6 12 h3 v12 h6 v-12 h3">
<path d="M312  52 l-6 12 h3 v12 h6 v-12 h3">
<path d="M424  52 l-6 12 h3 v12 h6 v-12 h3">
<path d="M60  100 l-6 12 h3 v12 h6 v-12 h3">
<path d="M116 100 l-6 12 h3 v12 h6 v-12 h3">
<path d="M172 100 l-6 12 h3 v12 h6 v-12 h3">
<path d="M230 100 l-6 12 h3 v12 h6 v-12 h3">
<path d="M284 100 l-6 12 h3 v12 h6 v-12 h3">
<path d="M340 100 l-6 12 h3 v12 h6 v-12 h3">
<path d="M396 100 l-6 12 h3 v12 h6 v-12 h3">
<path d="M452 100 l-6 12 h3 v12 h6 v-12 h3">
<path d="M46  148 l-6 12 h3 v12 h6 v-12 h3">
<path d="M74  148 l-6 12 h3 v12 h6 v-12 h3">
<path d="M102 148 l-6 12 h3 v12 h6 v-12 h3">
<path d="M130 148 l-6 12 h3 v12 h6 v-12 h3">
<path d="M158 148 l-6 12 h3 v12 h6 v-12 h3">
<path d="M186 148 l-6 12 h3 v12 h6 v-12 h3">
<path d="M214 148 l-6 12 h3 v12 h6 v-12 h3">
<path d="M242 148 l-6 12 h3 v12 h6 v-12 h3">
<path d="M270 148 l-6 12 h3 v12 h6 v-12 h3">
<path d="M298 148 l-6 12 h3 v12 h6 v-12 h3">
<path d="M326 148 l-6 12 h3 v12 h6 v-12 h3">
<path d="M354 148 l-6 12 h3 v12 h6 v-12 h3">
<path d="M382 148 l-6 12 h3 v12 h6 v-12 h3">
<path d="M410 148 l-6 12 h3 v12 h6 v-12 h3">
<path d="M438 148 l-6 12 h3 v12 h6 v-12 h3">
<path d="M466 148 l-6 12 h3 v12 h6 v-12 h3">
<path d="M39  196 l-6 12 h3 v12 h6 v-12 h3">
<path d="M53  196 l-6 12 h3 v12 h6 v-12 h3">
<path d="M67  196 l-6 12 h3 v12 h6 v-12 h3">
<path d="M81  196 l-6 12 h3 v12 h6 v-12 h3">
</g>
<g fill="black">
<path d="M32   32 v16 h1 v-16">
<path d="M256  32 v16 h1 v-16">
<path d="M480  32 v16 h1 v-16">
<path d="M32   32 h448 v1 h-448">
<path d="M32   48 h448 v1 h-448">
<path d="M32   80 v16 h1 v-16">
<path d="M144  80 v16 h1 v-16">
<path d="M256  80 v16 h1 v-16">
<path d="M368  80 v16 h1 v-16">
<path d="M480  80 v16 h1 v-16">
<path d="M32   80 h448 v1 h-448">
<path d="M32   96 h448 v1 h-448">
<path d="M32  128 v16 h1 v-16">
<path d="M88  128 v16 h1 v-16">
<path d="M144 128 v16 h1 v-16">
<path d="M200 128 v16 h1 v-16">
<path d="M256 128 v16 h1 v-16">
<path d="M312 128 v16 h1 v-16">
<path d="M368 128 v16 h1 v-16">
<path d="M424 128 v16 h1 v-16">
<path d="M480 128 v16 h1 v-16">
<path d="M32  128 h448 v1 h-448">
<path d="M32  144 h448 v1 h-448">
<path d="M32  176 v16 h1 v-16">
<path d="M60  176 v16 h1 v-16">
<path d="M88  176 v16 h1 v-16">
<path d="M116 176 v16 h1 v-16">
<path d="M144 176 v16 h1 v-16">
<path d="M172 176 v16 h1 v-16">
<path d="M200 176 v16 h1 v-16">
<path d="M228 176 v16 h1 v-16">
<path d="M256 176 v16 h1 v-16">
<path d="M284 176 v16 h1 v-16">
<path d="M312 176 v16 h1 v-16">
<path d="M340 176 v16 h1 v-16">
<path d="M368 176 v16 h1 v-16">
<path d="M396 176 v16 h1 v-16">
<path d="M424 176 v16 h1 v-16">
<path d="M452 176 v16 h1 v-16">
<path d="M480 176 v16 h1 v-16">
<path d="M32  176 h448 v1 h-448">
<path d="M32  192 h448 v1 h-448">
<path d="M32  224 v16 h1 v-16">
<path d="M46  224 v16 h1 v-16">
<path d="M60  224 v16 h1 v-16">
<path d="M74  224 v16 h1 v-16">
<path d="M88  224 v16 h1 v-16">
<path d="M102 224 v16 h1 v-16">
<path d="M116 224 v16 h1 v-16">
<path d="M130 224 v16 h1 v-16">
<path d="M144 224 v16 h1 v-16">
<path d="M158 224 v16 h1 v-16">
<path d="M172 224 v16 h1 v-16">
<path d="M186 224 v16 h1 v-16">
<path d="M200 224 v16 h1 v-16">
<path d="M214 224 v16 h1 v-16">
<path d="M228 224 v16 h1 v-16">
<path d="M242 224 v16 h1 v-16">
<path d="M256 224 v16 h1 v-16">
<path d="M270 224 v16 h1 v-16">
<path d="M284 224 v16 h1 v-16">
<path d="M298 224 v16 h1 v-16">
<path d="M312 224 v16 h1 v-16">
<path d="M326 224 v16 h1 v-16">
<path d="M340 224 v16 h1 v-16">
<path d="M354 224 v16 h1 v-16">
<path d="M368 224 v16 h1 v-16">
<path d="M382 224 v16 h1 v-16">
<path d="M396 224 v16 h1 v-16">
<path d="M410 224 v16 h1 v-16">
<path d="M424 224 v16 h1 v-16">
<path d="M438 224 v16 h1 v-16">
<path d="M452 224 v16 h1 v-16">
<path d="M466 224 v16 h1 v-16">
<path d="M480 224 v16 h1 v-16">
<path d="M32  224 h448 v1 h-448">
<path d="M32  240 h448 v1 h-448">
</g>
</svg>
title
<$FIGURE>
図２　ボトムアップ型
end title
@enduml
```

# ボトムアップ型の課題

非再帰型（ボトムアップ型）のマージソートにも面倒な課題がある。隣り合う二つの領域をマージするため，領域の数が奇数個だとマージするペアが足りなくて余ってしまう。また，基本的に結合を繰り返すたびに領域の大きさが１→２→４→８個と倍々ゲームで増えていくが，終端に限っては領域の大きさが不揃いになる。

図３に終端処理の場合分けを示す。配列の全要素数を $n$ とし，終端を除く領域の大きさを $s$ とすると以下の３つのケースに場合分けできる。

- $n \bmod 2s = 0$ のとき，過不足なく結合できる。
- $0 \le n \bmod 2s \le s$ のとき，終端部の要素は結合できずに余る。
- $s < n \bmod 2s < 2s$ のとき，終端部の要素も結合できるが二つの領域の大きさは異なる。

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
}
title {
  fontStyle normal
  fontSize 16
}
</style>
sprite FIGURE <svg width="624" height="300">
<g fill="lightblue">
<path d="M32  32 h32 v16 h-32">
<path d="M128 32 h64 v16 h-64">
<path d="M256 32 h64 v16 h-64">
<path d="M32  64 h32 v16 h-32">
<path d="M128 64 h64 v16 h-64">
<path d="M256 64 h64 v16 h-64">
<path d="M32  96 h32 v16 h-32">
<path d="M128 96 h64 v16 h-64">
<path d="M256 96 h64 v16 h-64">
<path d="M32  128 h32 v16 h-32">
<path d="M128 128 h64 v16 h-64">
<path d="M256 128 h64 v16 h-64">
<path d="M32  160 h32 v16 h-32">
<path d="M128 160 h64 v16 h-64">
<path d="M256 160 h64 v16 h-64">
<path d="M32  192 h32 v16 h-32">
<path d="M128 192 h64 v16 h-64">
<path d="M256 192 h64 v16 h-64">
<path d="M384 192 h16 v16 h-16">
<path d="M32  224 h32 v16 h-32">
<path d="M128 224 h64 v16 h-64">
<path d="M256 224 h64 v16 h-64">
<path d="M384 224 h32 v16 h-32">
<path d="M32  256 h32 v16 h-32">
<path d="M128 256 h64 v16 h-64">
<path d="M256 256 h64 v16 h-64">
<path d="M384 256 h48 v16 h-48">
</g>
<g fill="pink">
<path d="M64  32 h64 v16 h-64">
<path d="M192 32 h64 v16 h-64">
<path d="M64  64 h64 v16 h-64">
<path d="M192 64 h64 v16 h-64">
<path d="M64  96 h64 v16 h-64">
<path d="M192 96 h64 v16 h-64">
<path d="M64  128 h64 v16 h-64">
<path d="M192 128 h64 v16 h-64">
<path d="M64  160 h64 v16 h-64">
<path d="M192 160 h64 v16 h-64">
<path d="M64  192 h64 v16 h-64">
<path d="M192 192 h64 v16 h-64">
<path d="M320 192 h64 v16 h-64">
<path d="M64  224 h64 v16 h-64">
<path d="M192 224 h64 v16 h-64">
<path d="M320 224 h64 v16 h-64">
<path d="M64  256 h64 v16 h-64">
<path d="M192 256 h64 v16 h-64">
<path d="M320 256 h64 v16 h-64">
</g>
<g fill="black">
<path d="M256 24 h8 v1 h-8" transform="rotate(22.5,256,24)" />
<path d="M256 24 h8 v1 h-8" transform="rotate(-22.5,256,24)" />
<path d="M320 24 h-8 v1 h8" transform="rotate(22.5,320,24)" />
<path d="M320 24 h-8 v1 h8" transform="rotate(-22.5,320,24)" />
<path d="M256 24 h64 v1 h-64">
<path d="M32 32 h288 v1 h-288">
<path d="M32 48 h288 v1 h-288">
<path d="M64  32 v16 h1 v-16">
<path d="M128 32 v16 h1 v-16">
<path d="M192 32 v16 h1 v-16">
<path d="M256 32 v16 h1 v-16">
<path d="M320 32 v16 h1 v-16">
<path d="M32 64 h304 v1 h-304">
<path d="M32 80 h304 v1 h-304">
<path d="M64  64 v16 h1 v-16">
<path d="M128 64 v16 h1 v-16">
<path d="M192 64 v16 h1 v-16">
<path d="M256 64 v16 h1 v-16">
<path d="M320 64 v16 h1 v-16">
<path d="M336 64 v16 h1 v-16">
<path d="M32  96 h320 v1 h-320">
<path d="M32 112 h320 v1 h-320">
<path d="M64  96 v16 h1 v-16">
<path d="M128 96 v16 h1 v-16">
<path d="M192 96 v16 h1 v-16">
<path d="M256 96 v16 h1 v-16">
<path d="M320 96 v16 h1 v-16">
<path d="M336 96 v16 h1 v-16">
<path d="M352 96 v16 h1 v-16">
<path d="M32  128 h336 v1 h-336">
<path d="M32  144 h336 v1 h-336">
<path d="M64  128 v16 h1 v-16">
<path d="M128 128 v16 h1 v-16">
<path d="M192 128 v16 h1 v-16">
<path d="M256 128 v16 h1 v-16">
<path d="M320 128 v16 h1 v-16">
<path d="M336 128 v16 h1 v-16">
<path d="M352 128 v16 h1 v-16">
<path d="M368 128 v16 h1 v-16">
<path d="M32  160 h352 v1 h-352">
<path d="M32  176 h352 v1 h-352">
<path d="M64  160 v16 h1 v-16">
<path d="M128 160 v16 h1 v-16">
<path d="M192 160 v16 h1 v-16">
<path d="M256 160 v16 h1 v-16">
<path d="M320 160 v16 h1 v-16">
<path d="M336 160 v16 h1 v-16">
<path d="M352 160 v16 h1 v-16">
<path d="M368 160 v16 h1 v-16">
<path d="M384 160 v16 h1 v-16">
<path d="M32  192 h368 v1 h-368">
<path d="M32  208 h368 v1 h-368">
<path d="M64  192 v16 h1 v-16">
<path d="M128 192 v16 h1 v-16">
<path d="M192 192 v16 h1 v-16">
<path d="M256 192 v16 h1 v-16">
<path d="M320 192 v16 h1 v-16">
<path d="M336 192 v16 h1 v-16">
<path d="M352 192 v16 h1 v-16">
<path d="M368 192 v16 h1 v-16">
<path d="M384 192 v16 h1 v-16">
<path d="M400 192 v16 h1 v-16">
<path d="M32  224 h384 v1 h-384">
<path d="M32  240 h384 v1 h-384">
<path d="M64  224 v16 h1 v-16">
<path d="M128 224 v16 h1 v-16">
<path d="M192 224 v16 h1 v-16">
<path d="M256 224 v16 h1 v-16">
<path d="M320 224 v16 h1 v-16">
<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="M32  256 h400 v1 h-400">
<path d="M32  272 h400 v1 h-400">
<path d="M64  256 v16 h1 v-16">
<path d="M128 256 v16 h1 v-16">
<path d="M192 256 v16 h1 v-16">
<path d="M256 256 v16 h1 v-16">
<path d="M320 256 v16 h1 v-16">
<path d="M336 256 v16 h1 v-16">
<path d="M352 256 v16 h1 v-16">
<path d="M368 256 v16 h1 v-16">
<path d="M384 256 v16 h1 v-16">
<path d="M400 256 v16 h1 v-16">
<path d="M416 256 v16 h1 v-16">
<path d="M432 256 v16 h1 v-16">
<path d="M400 64 v112 h1 v-112">
<path d="M392 64  h8 v1 h-8">
<path d="M392 176 h8 v1 h-8">
<path d="M448 192 v80 h1 v-80">
<path d="M440 192 h8 v1 h-8">
<path d="M440 272 h8 v1 h-8">
</g>
<text x="284" y="20" font-size="16" fill="black">s</text>
<text x="328" y="46"  font-size="16" fill="black">n mod 2s = 0</text>
<text x="408" y="126" font-size="16" fill="black">0 < n mod 2s ≤ s</text>
<text x="456" y="238" font-size="16" fill="black">s < n mod 2s < 2s</text>
</svg>
title
<$FIGURE>
図３　終端処理がややこしい
end title
@enduml
```

# ソースコード全容

ということで非再帰型（ボトムアップ型）に書き換えたマージソートのコードを以下に示す。大して長くはないので，まずは全容を示そう。

```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 = 0; 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, adj;
/* 032 */         for(i = 0; i + s * 2 < len; i += s * 2)
/* 033 */             merge(buf, &a[i], s, s, compare);
/* 034 */         if((adj = len - (i + s)) > 0)
/* 035 */             merge(buf, &a[i], s, adj, compare);
/* 036 */     }
/* 037 */ }
/* 038 */ void    msort(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 */ }
```

# アルゴリズム解説

それでは頭から解説したい。

## 1. 交換関数

まずは，交換関数 `swap()` である。`qsort_ucrt` で用いたものと全く同じである。

```c++:交換関数
/* 004 */ static  void    swap(int *p, int *q) {
/* 005 */     int temp = *p;
/* 006 */     *p = *q;
/* 007 */     *q = temp;
/* 008 */ }
```

## 2. ソート関数本体の冒頭部分

ソート関数本体 `msort()` の冒頭部分である。関数の名前が違うだけで中身は `qsort_glibc()` と全く同じである。

```c++:ソート関数本体の冒頭部分
/* 001 */ #include <stdlib.h>
/* 002 */ typedef int     (*COMPARE)(int, int);
/* 003 */ #define TEMP_SIZE   256

/* 038 */ void    msort(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 */ }
```

## 3. マージソートエンジン

マージソートエンジン `sort` の引数も `qsort_glibc` と変わらないが，再帰呼び出しではなく，ループ処理にてマージを進めていく。

28～29行は領域の大きさが１の場合のマージ処理である。隣接する要素の大小を比較して入れ替えれば良いので，交換関数 `swap` の呼び出しで済ませている。

30～36行は領域の大きさ `s` が２以上の場合のマージ処理である。領域の大きさ `s` が配列の要素数 `len` 以上になれば終了となる。

32～33行はマージする二つの領域の大きさが同じ場合の処理である。

34～35行は終端処理である。

```c++
/* 027 */ static  void    sort(int *buf, int *a, int len, COMPARE compare) {
/* 028 */     for(int i = 0; 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, adj;
/* 032 */         for(i = 0; i + s * 2 < len; i += s * 2)
/* 033 */             merge(buf, &a[i], s, s, compare);
/* 034 */         if((adj = len - (i + s)) > 0)
/* 035 */             merge(buf, &a[i], s, adj, compare);
/* 036 */     }
/* 037 */ }
```

## 4. マージ関数

マージのアルゴリズムは `qsort_glibc` と同じである。配列 `a[]` の先頭から `n1` 個と，それに続く `n2` 個の要素のマージであり，後半部の `n2` 個の要素が余った場合，コピー処理を省略するなどの工夫が施されている。

```c++
/* 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 */ }
```

# バイナリサイズの比較

バイナリサイズの比較を以下に示す。

- uCRT：クイックソート，uCRT 版 `qsort` の意訳版
- glibc：再帰型マージソート，GNU C ライブラリの `qsort` の意訳版
- merge：非再帰型マージソート　※今回作成したもの

<table>
<caption>表１　バイナリサイズの比較（単位はバイト）</caption>
<thead>
<tr><th colspan=2 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></tr>
</thead>
<tbody>
<tr></tr>
<tr><th rowspan=3>Visual C++</th>
    <th>32bit</th>
    <td style="text-align:right">118,272</td>
    <td style="text-align:right">117,760</td>
    <td style="text-align:right">118,272</td></tr>
<tr></tr>
<tr><th>64bit</th>
    <td style="text-align:right">142,848</td>
    <td style="text-align:right">142,848</td>
    <td style="text-align:right">142,848</td></tr>
<tr></tr>
<tr><th rowspan=3>LLVM clang-cl</th>
    <th>32bit</th>
    <td style="text-align:right">118,784</td>
    <td style="text-align:right">118,784</td>
    <td style="text-align:right">119,296</td></tr>
<tr></tr>
<tr><th>64bit</th>
    <td style="text-align:right">148,480</td>
    <td style="text-align:right">148,480</td>
    <td style="text-align:right">148,992</td></tr>
<tr></tr>
<tr><th rowspan=3>intel icx-cl</th>
    <th>32bit</th>
    <td style="text-align:right">166,400</td>
    <td style="text-align:right">169,472</td><td style="text-align:right">169,984</td></tr>
<tr></tr>
<tr><th>64bit</th>
    <td style="text-align:right">208,384</td>
    <td style="text-align:right">226,304</td>
    <td style="text-align:right">227,328</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">uCRT</th>
    <th style="text-align:center">glibc</th>
    <th style="text-align:center">merge</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></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></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></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></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></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></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></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></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></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></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></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></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></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></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></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></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></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></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></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></tr>
<tr></tr>
<tr><th rowspan=7>intel icx-cl<br>64bit版</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></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></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></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></tr>
</tbody>
</table>

グラフにすると分かり易い。

<font color=#589BD5>■</font>uCRT，<font color=#ED7D31>■</font>glibc，<font color=#A5A5A5>■</font>merge

```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="50"  y="350" font-size="16" fill="black">ゼロ</text>
<text x="120" y="350" font-size="16" fill="black">昇順</text>
<text x="190" y="350" font-size="16" fill="black">降順</text>
<text x="260" y="350" font-size="16" fill="black">乱数</text>
<g fill="#5B9BD5">
<path d="M42 330 h14 v-1 h-14">
<path d="M112 330 h14 v-17 h-14">
<path d="M182 330 h14 v-18 h-14">
<path d="M252 330 h14 v-186 h-14">
</g>
<g fill="#ED7D31">
<path d="M58 330 h14 v-32 h-14">
<path d="M128 330 h14 v-32 h-14">
<path d="M198 330 h14 v-47 h-14">
<path d="M268 330 h14 v-216 h-14">
</g>
<g fill="#A5A5A5">
<path d="M74 330 h14 v-34 h-14">
<path d="M144 330 h14 v-34 h-14">
<path d="M214 330 h14 v-56 h-14">
<path d="M284 330 h14 v-233 h-14">
</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="50"  y="350" font-size="16" fill="black">ゼロ</text>
<text x="120" y="350" font-size="16" fill="black">昇順</text>
<text x="190" y="350" font-size="16" fill="black">降順</text>
<text x="260" y="350" font-size="16" fill="black">乱数</text>
<g fill="#5B9BD5">
<path d="M42 330 h14 v-1 h-14">
<path d="M112 330 h14 v-19 h-14">
<path d="M182 330 h14 v-19 h-14">
<path d="M252 330 h14 v-186 h-14">
</g>
<g fill="#ED7D31">
<path d="M58 330 h14 v-30 h-14">
<path d="M128 330 h14 v-30 h-14">
<path d="M198 330 h14 v-45 h-14">
<path d="M268 330 h14 v-254 h-14">
</g>
<g fill="#A5A5A5">
<path d="M74 330 h14 v-26 h-14">
<path d="M144 330 h14 v-26 h-14">
<path d="M214 330 h14 v-40 h-14">
<path d="M284 330 h14 v-241 h-14">
</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">
<path d="M30 330 h280 v1 h-280" fill="lightgray">
<path d="M30 270 h280 v1 h-280" fill="lightgray">
<path d="M30 210 h280 v1 h-280" fill="lightgray">
<path d="M30 150 h280 v1 h-280" fill="lightgray">
<path d="M30  90 h280 v1 h-280" fill="lightgray">
<path d="M30  30 h280 v1 h-280" fill="lightgray">
<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="50"  y="350" font-size="16" fill="black">ゼロ</text>
<text x="120" y="350" font-size="16" fill="black">昇順</text>
<text x="190" y="350" font-size="16" fill="black">降順</text>
<text x="260" y="350" font-size="16" fill="black">乱数</text>
<g fill="#5B9BD5">
<path d="M42 330 h14 v-1 h-14">
<path d="M112 330 h14 v-20 h-14">
<path d="M182 330 h14 v-20 h-14">
<path d="M252 330 h14 v-188 h-14">
</g>
<g fill="#ED7D31">
<path d="M58 330 h14 v-25 h-14">
<path d="M128 330 h14 v-25 h-14">
<path d="M198 330 h14 v-44 h-14">
<path d="M268 330 h14 v-198 h-14">
</g>
<g fill="#A5A5A5">
<path d="M74 330 h14 v-25 h-14">
<path d="M144 330 h14 v-25 h-14">
<path d="M214 330 h14 v-36 h-14">
<path d="M284 330 h14 v-192 h-14">
</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">
<path d="M30 330 h280 v1 h-280" fill="lightgray">
<path d="M30 270 h280 v1 h-280" fill="lightgray">
<path d="M30 210 h280 v1 h-280" fill="lightgray">
<path d="M30 150 h280 v1 h-280" fill="lightgray">
<path d="M30  90 h280 v1 h-280" fill="lightgray">
<path d="M30  30 h280 v1 h-280" fill="lightgray">
<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="50"  y="350" font-size="16" fill="black">ゼロ</text>
<text x="120" y="350" font-size="16" fill="black">昇順</text>
<text x="190" y="350" font-size="16" fill="black">降順</text>
<text x="260" y="350" font-size="16" fill="black">乱数</text>
<g fill="#5B9BD5">
<path d="M42 330 h14 v-1 h-14">
<path d="M112 330 h14 v-18 h-14">
<path d="M182 330 h14 v-18 h-14">
<path d="M252 330 h14 v-189 h-14">
</g>
<g fill="#ED7D31">
<path d="M58 330 h14 v-23 h-14">
<path d="M128 330 h14 v-24 h-14">
<path d="M198 330 h14 v-35 h-14">
<path d="M268 330 h14 v-192 h-14">
</g>
<g fill="#A5A5A5">
<path d="M74 330 h14 v-20 h-14">
<path d="M144 330 h14 v-20 h-14">
<path d="M214 330 h14 v-29 h-14">
<path d="M284 330 h14 v-190 h-14">
</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">
<path d="M30 330 h280 v1 h-280" fill="lightgray">
<path d="M30 270 h280 v1 h-280" fill="lightgray">
<path d="M30 210 h280 v1 h-280" fill="lightgray">
<path d="M30 150 h280 v1 h-280" fill="lightgray">
<path d="M30  90 h280 v1 h-280" fill="lightgray">
<path d="M30  30 h280 v1 h-280" fill="lightgray">
<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="50"  y="350" font-size="16" fill="black">ゼロ</text>
<text x="120" y="350" font-size="16" fill="black">昇順</text>
<text x="190" y="350" font-size="16" fill="black">降順</text>
<text x="260" y="350" font-size="16" fill="black">乱数</text>
<g fill="#5B9BD5">
<path d="M42 330 h14 v-1 h-14">
<path d="M112 330 h14 v-19 h-14">
<path d="M182 330 h14 v-20 h-14">
<path d="M252 330 h14 v-205 h-14">
</g>
<g fill="#ED7D31">
<path d="M58 330 h14 v-30 h-14">
<path d="M128 330 h14 v-30 h-14">
<path d="M198 330 h14 v-40 h-14">
<path d="M268 330 h14 v-214 h-14">
</g>
<g fill="#A5A5A5">
<path d="M74 330 h14 v-24 h-14">
<path d="M144 330 h14 v-25 h-14">
<path d="M214 330 h14 v-35 h-14">
<path d="M284 330 h14 v-213 h-14">
</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">
<path d="M30 330 h280 v1 h-280" fill="lightgray">
<path d="M30 270 h280 v1 h-280" fill="lightgray">
<path d="M30 210 h280 v1 h-280" fill="lightgray">
<path d="M30 150 h280 v1 h-280" fill="lightgray">
<path d="M30  90 h280 v1 h-280" fill="lightgray">
<path d="M30  30 h280 v1 h-280" fill="lightgray">
<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="50"  y="350" font-size="16" fill="black">ゼロ</text>
<text x="120" y="350" font-size="16" fill="black">昇順</text>
<text x="190" y="350" font-size="16" fill="black">降順</text>
<text x="260" y="350" font-size="16" fill="black">乱数</text>
<g fill="#5B9BD5">
<path d="M42 330 h14 v-1 h-14">
<path d="M112 330 h14 v-16 h-14">
<path d="M182 330 h14 v-18 h-14">
<path d="M252 330 h14 v-199 h-14">
</g>
<g fill="#ED7D31">
<path d="M58 330 h14 v-22 h-14">
<path d="M128 330 h14 v-22 h-14">
<path d="M198 330 h14 v-30 h-14">
<path d="M268 330 h14 v-192 h-14">
</g>
<g fill="#A5A5A5">
<path d="M74 330 h14 v-19 h-14">
<path d="M144 330 h14 v-19 h-14">
<path d="M214 330 h14 v-29 h-14">
<path d="M284 330 h14 v-188 h-14">
</g>
</svg>
title
<$FIGURE>
図６　intel icx-cl 64bit版（単位は秒）
end title
@enduml
```

# 結論

参考文献（JavaScript）では「非再帰型のマージソートは驚くほど高速化した」とあるが，残念ながら筆者のＣコードでは非再帰型にすることで逆に悪くなったコンパイラもあるので評価が悩ましいところ。もちろん速くなったものもあるが，高速化の割合は微々たるものである。

# 次回

次回に続く。

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

<!--
# 参考文献
-->

[^1]: [再帰なしのマージソート - WordPress](https://6esky.wordpress.com/2009/05/23/再帰なしのマージソート/)

[^2]: [再帰なしでマージソートやってみたら驚くほど高速化した話 - HatenaBlog](https://konbu13.hatenablog.com/entry/2014/02/11/195731)

[^3]: [アルゴリズムとデータ構造編【整列アルゴリズム】 第７章 - Programming Place Plus](https://programming-place.net/ppp/contents/algorithm/sort/007.html)