マージソートを非再帰型に書き直す４～限界突破のアイディアを思いつく～

# はじめに

これまで下記の記事で 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)
- [マージソートを非再帰型に書き直す３～もう限界かもしれない～ - Qiita](https://qiita.com/TETSURO1999/items/5aa007604198b2ff7b06)

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

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

だがしかし，先日，パフォーマンスアップを期待できるアイディアを思いついたのだ。

# 改善案

部屋の模様替えを行うとき，部屋が狭いわりに大きな家具や荷物が多いといろいろ悩ましい。まず，移動先の空きスペースを確保しないといけないし，かつての倉庫番ゲームのように動かす順番を考えないといけないからだ。こういうとき隣の部屋が空いていたりするととても便利である。ある日，ふと思いついたのだ。いっそのこと隣の空き部屋に家具を全部持って行ってそこに住んでしまえばいいんじゃねと？

マージソートでも同様だ。マージソートでは基本的にソート対象となる配列と同サイズの作業用エリアを必要とする。二つの区間をマージする際，いったん作業用エリア上でマージして，それから元の配列に書き戻しているのだが，わざわざ書き戻さなくても良くないか？つまり，作業用エリアをそのまま使ってしまい，今度は元の配列の領域を作業用として使おうというアイディアだ。こうして二つのエリアを交互に作業用として使えば，データ転送量を約半分に済ませられるはず。

ちなみにこのアイディアは非再帰型（ボトムアップ型）マージソートでないと成立しない。

# 実装コード

とても簡単にできたので全容を示そう。

```c++:merge4（ボトムアップ型・データ転送節約版）
/* 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 *p1 = a;
/* 011 */     int *p2 = a + n1;
/* 012 */     int *q = buf;
/* 013 */     for(;;) {
/* 014 */         if(compare(*p1, *p2) <= 0) {
/* 015 */             *q++ = *p1++; if(--n1 == 0) break;
/* 016 */         } else {
/* 017 */             *q++ = *p2++; if(--n2 == 0) break;
/* 018 */         }
/* 019 */     }
/* 020 */     while(n1 > 0) {
/* 021 */         *q++ = *p1++; n1--;
/* 022 */     }
/* 023 */     while(n2 > 0) {
/* 024 */         *q++ = *p2++; n2--;
/* 025 */     }
/* 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 */     int *x = a;
/* 031 */     int *y = buf;
/* 032 */     for(int s = 2; s < len; s = s * 2) {
/* 033 */         int i, adj;
/* 034 */         for(i = 0; i + s * 2 < len; i += s * 2)
/* 035 */             merge(&y[i], &x[i], s, s, compare);
/* 036 */         if((adj = len - (i + s)) > 0)
/* 037 */             merge(&y[i], &x[i], s, adj, compare);
/* 038 */         else
/* 039 */             for(; i < len; i++) y[i] = x[i];
/* 040 */         int *temp = x; x = y; y = temp;
/* 041 */     }
/* 042 */     if(x != a)
/* 043 */         for(int i = 0; i < len; i++) a[i] = x[i];
/* 044 */ }
/* 045 */ void    msort4(int *a, int len, COMPARE compare) {
/* 046 */     if(len < 2) return;
/* 047 */     if(len <= TEMP_SIZE) {
/* 048 */         int tmp[TEMP_SIZE];
/* 049 */         sort(tmp, a, len, compare);
/* 050 */     } else {
/* 051 */         int *buf = (int*)malloc(sizeof(int) * len);
/* 052 */         if(buf == (int*)NULL) return;
/* 053 */         sort(buf, a, len, compare);
/* 054 */         free(buf);
/* 055 */     }
/* 056 */ }
/* 057 */ 
```

# アルゴリズム解説

それでは自作コードを頭から解説していきたい。同じ非再帰型（ボトムアップ型）マージソートと比べれば実装の違いがよく分かると思う。

[マージソートを非再帰型に書き直す～誰でも思いつくアイディアだが～ - Qiita](https://qiita.com/TETSURO1999/items/23bdd493975cbd8a5085)

## 1. 交換関数

交換関数 `swap` は全く同じである。

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
  backgroundColor #202020
}
title {
  horizontalAlignment left
  padding 0 0 4 6
  fontColor #e3e3e3
  fontStyle normal
  fontName monospaced
  fontSize 14
}
</style>
sprite TITLE <svg width="340" height="32">
<path d="M0 0 v18 a6 6 0 0 0 6 6 h164 a 6 6 0 0 0 6 -6 v-18" fill="#606060">
<text x="6" y="18" font-size="14" fill="white">merge（ボトムアップ型）</text>
</svg>
title
<$TITLE>
<color:#ebd247>static  void</color>  <color:#8bdf4c>swap</color>(<color:#ebd247>int</color> <color:#ff8095>*</color>p, <color:#ebd247>int</color> <color:#ff8095>*</color>q) {
  <color:#ebd247>int</color> temp <color:#ff8095>=</color> <color:#ff8095>*</color>p;
  <color:#ff8095>*</color>p <color:#ff8095>= *</color>q;
  <color:#ff8095>*</color>q <color:#ff8095>=</color> temp;
}
end title
@enduml
```

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
  backgroundColor #202020
}
title {
  horizontalAlignment left
  padding 0 0 4 6
  fontColor #e3e3e3
  fontStyle normal
  fontName monospaced
  fontSize 14
}
</style>
sprite TITLE <svg width="340" height="32">
<path d="M0 0 v18 a6 6 0 0 0 6 6 h298 a 6 6 0 0 0 6 -6 v-18" fill="#606060">
<text x="6" y="18" font-size="14" fill="white">merge4（ボトムアップ型・データ転送節約版）</text>
</svg>
title
<$TITLE>
<color:#ebd247>static  void</color>  <color:#8bdf4c>swap</color>(<color:#ebd247>int</color> <color:#ff8095>*</color>p, <color:#ebd247>int</color> <color:#ff8095>*</color>q) {
  <color:#ebd247>int</color> temp <color:#ff8095>=</color> <color:#ff8095>*</color>p;
  <color:#ff8095>*</color>p <color:#ff8095>= *</color>q;
  <color:#ff8095>*</color>q <color:#ff8095>=</color> temp;
}
end title
@enduml
```

## 2. ソート関数本体

ソート関数本体である。関数名のみ異なり，あとは全く同じである。

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
  backgroundColor #202020
}
title {
  horizontalAlignment left
  padding 0 0 4 6
  fontColor #e3e3e3
  fontStyle normal
  fontName monospaced
  fontSize 14
}
</style>
sprite TITLE <svg width="340" height="32">
<path d="M0 0 v18 a6 6 0 0 0 6 6 h164 a 6 6 0 0 0 6 -6 v-18" fill="#606060">
<text x="6" y="18" font-size="14" fill="white">merge（ボトムアップ型）</text>
</svg>
title
<$TITLE>
<color:#979797>#include <U+003C>stdlib.h<U+003E></color>
<color:#ebd247>typedef</color> <color:#8bdf4c>int</color>   (<color:#ff8095>*</color>COMPARE)(<color:#ebd247>int</color>, <color:#ebd247>int</color>);
<color:#979797>#define TEMP_SIZE 256</color>

<color:#ebd247>void</color>  <color:#8bdf4c>msort</color>(
  <color:#ebd247>int</color> <color:#ff8095>*</color>a, <color:#ebd247>int</color> len, COMPARE compare) {
  <color:#ebd247>if</color>(len <color:#ff8095><U+003C></color> <color:#a980f5>2</color>) <color:#ebd247>return</color>;
  <color:#ebd247>if</color>(len <color:#ff8095><U+003C>=</color> TEMP_SIZE) {
    <color:#ebd247>int</color> tmp[TEMP_SIZE];
    sort(tmp, a, len, compare);
  } <color:#ebd247>else</color> {
    <color:#ebd247>int</color> <color:#ff8095>*</color>buf <color:#ff8095>=</color> malloc(<color:#ebd247>sizeof</color>(<color:#ebd247>int</color>) <color:#ff8095>*</color> len);
    <color:#ebd247>if</color>(buf <color:#ff8095>==</color> (<color:#ebd247>int</color><color:#ff8095>*</color>)NULL) <color:#ebd247>return</color>;
    sort(buf, a, len, compare);
    free(buf);
  }
}
end title
@enduml
```

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
  backgroundColor #202020
}
title {
  horizontalAlignment left
  padding 0 0 4 6
  fontColor #e3e3e3
  fontStyle normal
  fontName monospaced
  fontSize 14
}
</style>
sprite TITLE <svg width="340" height="32">
<path d="M0 0 v18 a6 6 0 0 0 6 6 h298 a 6 6 0 0 0 6 -6 v-18" fill="#606060">
<text x="6" y="18" font-size="14" fill="white">merge4（ボトムアップ型・データ転送節約版）</text>
</svg>
title
<$TITLE>
<color:#979797>#include <U+003C>stdlib.h<U+003E></color>
<color:#ebd247>typedef</color> <color:#8bdf4c>int</color>   (<color:#ff8095>*</color>COMPARE)(<color:#ebd247>int</color>, <color:#ebd247>int</color>);
<color:#979797>#define TEMP_SIZE 256</color>

<color:#ebd247>void</color>  <color:#8bdf4c>msort4</color>(
  <color:#ebd247>int</color> <color:#ff8095>*</color>a, <color:#ebd247>int</color> len, COMPARE compare) {
  <color:#ebd247>if</color>(len <color:#ff8095><U+003C></color> <color:#a980f5>2</color>) <color:#ebd247>return</color>;
  <color:#ebd247>if</color>(len <color:#ff8095><U+003C>=</color> TEMP_SIZE) {
    <color:#ebd247>int</color> tmp[TEMP_SIZE];
    sort(tmp, a, len, compare);
  } <color:#ebd247>else</color> {
    <color:#ebd247>int</color> <color:#ff8095>*</color>buf <color:#ff8095>=</color> malloc(<color:#ebd247>sizeof</color>(<color:#ebd247>int</color>) <color:#ff8095>*</color> len);
    <color:#ebd247>if</color>(buf <color:#ff8095>==</color> (<color:#ebd247>int</color><color:#ff8095>*</color>)NULL) <color:#ebd247>return</color>;
    sort(buf, a, len, compare);
    free(buf);
  }
}
end title
@enduml
```

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

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

領域の大きさ `s` が２以上になると本実装の特徴が表れる。元の配列 `a[]` と作業用エリア `buf[]` を直接参照せず，読出し側が `x`，書き込み側が `y` とポインタによる間接参照にして，マージを一段実行する毎にポインタ `x` と `y` を交換しているのだ。

他に注意事項としては以下の二つ。
- 末尾にある未結合要素も忘れずにコピーする必要がある
- 最後に元の配列 `a[]` に書き戻すことを忘れないこと

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
  backgroundColor #202020
}
title {
  horizontalAlignment left
  padding 0 0 4 4
  fontColor #e3e3e3
  fontStyle normal
  fontName monospaced
  fontSize 14
}
</style>
sprite TITLE <svg width="340" height="32">
<path d="M0 0 v18 a6 6 0 0 0 6 6 h164 a 6 6 0 0 0 6 -6 v-18" fill="#606060">
<text x="6" y="18" font-size="14" fill="white">merge（ボトムアップ型）</text>
</svg>
title
<$TITLE>
<color:#ebd247>static  void</color>  <color:#8bdf4c>sort</color>(
  <color:#ebd247>int</color> <color:#ff8095>*</color>buf, <color:#ebd247>int</color> <color:#ff8095>*</color>a, <color:#ebd247>int</color> len,
    COMPARE compare) {
  <color:#ebd247>for</color>(<color:#ebd247>int</color> i <color:#ff8095>=</color> <color:#a980f5>0</color>; i <color:#ff8095>+</color> <color:#a980f5>1</color> <color:#ff8095><U+003C></color> len; i <color:#ff8095>+=</color> <color:#a980f5>2</color>)
    <color:#ebd247>if</color>(compare(a[i], a[i <color:#ff8095>+</color> <color:#a980f5>1</color>]) <color:#ff8095><U+003E></color> <color:#a980f5>0</color>)
      swap(<color:#ff8095>&</color>a[i], <color:#ff8095>&</color>a[i <color:#ff8095>+</color> <color:#a980f5>1</color>]);


  <color:#ebd247>for</color>(<color:#ebd247>int</color> s <color:#ff8095>=</color> <color:#a980f5>2</color>; s <color:#ff8095><U+003C></color> len; s <color:#ff8095>=</color> s <color:#ff8095>*</color> <color:#a980f5>2</color>) {
    <color:#ebd247>int</color> i, adj;
    <color:#ebd247>for</color>(i <color:#ff8095>=</color> <color:#a980f5>0</color>; i <color:#ff8095>+</color> s <color:#ff8095>*</color> <color:#a980f5>2</color> <color:#ff8095><U+003C></color> len; i <color:#ff8095>+=</color> s <color:#ff8095>*</color> <color:#a980f5>2</color>)
      merge(buf, <color:#ff8095>&</color>a[i], s, s, compare);
    <color:#ebd247>if</color>((adj <color:#ff8095>=</color> len <color:#ff8095>-</color> (i <color:#ff8095>+</color> s)) <color:#ff8095><U+003E></color> <color:#a980f5>0</color>)
      merge(buf, <color:#ff8095>&</color>a[i], s, adj, compare);



  }



}
end title
@enduml
```

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
  backgroundColor #202020
}
title {
  horizontalAlignment left
  padding 0 0 4 4
  fontColor #e3e3e3
  fontStyle normal
  fontName monospaced
  fontSize 14
}
</style>
sprite TITLE <svg width="340" height="32">
<path d="M0 0 v18 a6 6 0 0 0 6 6 h298 a 6 6 0 0 0 6 -6 v-18" fill="#606060">
<text x="6" y="18" font-size="14" fill="white">merge4（ボトムアップ型・データ転送節約版）</text>
</svg>
title
<$TITLE>
<color:#ebd247>static  void</color>  <color:#8bdf4c>sort</color>(
  <color:#ebd247>int</color> <color:#ff8095>*</color>buf, <color:#ebd247>int</color> <color:#ff8095>*</color>a, <color:#ebd247>int</color> len,
    COMPARE compare) {
  <color:#ebd247>for</color>(<color:#ebd247>int</color> i <color:#ff8095>=</color> <color:#a980f5>0</color>; i <color:#ff8095>+</color> <color:#a980f5>1</color> <color:#ff8095><U+003C></color> len; i <color:#ff8095>+=</color> <color:#a980f5>2</color>)
    <color:#ebd247>if</color>(compare(a[i], a[i <color:#ff8095>+</color> <color:#a980f5>1</color>]) <color:#ff8095><U+003E></color> <color:#a980f5>0</color>)
      swap(<color:#ff8095>&</color>a[i], <color:#ff8095>&</color>a[i <color:#ff8095>+</color> <color:#a980f5>1</color>]);
  <color:#ebd247>int</color> <color:#ff8095>*</color>x <color:#ff8095>=</color> a;
  <color:#ebd247>int</color> <color:#ff8095>*</color>y <color:#ff8095>=</color> buf;
  <color:#ebd247>for</color>(<color:#ebd247>int</color> s <color:#ff8095>=</color> <color:#a980f5>2</color>; s <color:#ff8095><U+003C></color> len; s <color:#ff8095>=</color> s <color:#ff8095>*</color> <color:#a980f5>2</color>) {
    <color:#ebd247>int</color> i, adj;
    <color:#ebd247>for</color>(i <color:#ff8095>=</color> <color:#a980f5>0</color>; i <color:#ff8095>+</color> s <color:#ff8095>*</color> <color:#a980f5>2</color> <color:#ff8095><U+003C></color> len; i <color:#ff8095>+=</color> s <color:#ff8095>*</color> <color:#a980f5>2</color>)
      merge(<color:#ff8095>&</color>y[i], <color:#ff8095>&</color>x[i], s, s, compare);
    <color:#ebd247>if</color>((adj <color:#ff8095>=</color> len <color:#ff8095>-</color> (i <color:#ff8095>+</color> s)) <color:#ff8095><U+003E></color> <color:#a980f5>0</color>)
      merge(<color:#ff8095>&</color>y[i], <color:#ff8095>&</color>x[i], s, adj, compare);
    <color:#ebd247>else</color>
      <color:#ebd247>for</color>(; i <color:#ff8095><U+003C></color> len; i<color:#ff8095>++</color>) y[i] <color:#ff8095>=</color> x[i];
    <color:#ebd247>int</color> <color:#ff8095>*</color>temp <color:#ff8095>=</color> x; x <color:#ff8095>=</color> y; y <color:#ff8095>=</color> temp;
  }
  <color:#ebd247>if</color>(x <color:#ff8095>!=</color> a)
    <color:#ebd247>for</color>(<color:#ebd247>int</color> i <color:#ff8095>=</color> <color:#a980f5>0</color>; i <color:#ff8095><U+003C></color> len; i<color:#ff8095>++</color>)
      a[i] <color:#ff8095>=</color> x[i];
}
end title
@enduml
```
## 4. マージ関数

マージ関数も少し違う。作業用エリア `buf[]` に書き込むのみで元の配列 `a[]` に書き戻さない。

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
  backgroundColor #202020
}
title {
  horizontalAlignment left
  padding 0 0 4 6
  fontColor #e3e3e3
  fontStyle normal
  fontName monospaced
  fontSize 14
}
</style>
sprite TITLE <svg width="340" height="32">
<path d="M0 0 v18 a6 6 0 0 0 6 6 h164 a 6 6 0 0 0 6 -6 v-18" fill="#606060">
<text x="6" y="18" font-size="14" fill="white">merge（ボトムアップ型）</text>
</svg>
title
<$TITLE>
<color:#ebd247>static  void</color>  <color:#8bdf4c>merge</color>(
  <color:#ebd247>int</color> <color:#ff8095>*</color>buf, <color:#ebd247>int</color> <color:#ff8095>*</color>a, <color:#ebd247>int</color> n1, <color:#ebd247>int</color> n2,
    COMPARE compare) {
  <color:#ebd247>int</color> n <color:#ff8095>=</color> n1 <color:#ff8095>+</color> n2;
  <color:#ebd247>int</color> <color:#ff8095>*</color>p1 <color:#ff8095>=</color> a;
  <color:#ebd247>int</color> <color:#ff8095>*</color>p2 <color:#ff8095>=</color> a <color:#ff8095>+</color> n1;
  <color:#ebd247>int</color> <color:#ff8095>*</color>q <color:#ff8095>=</color> buf;
  <color:#ebd247>for</color>(;;) {
    <color:#ebd247>if</color>(compare(<color:#ff8095>*</color>p1, <color:#ff8095>*</color>p2) <color:#ff8095><U+003C>=</color> <color:#a980f5>0</color>) {
      <color:#ff8095>*</color>q<color:#ff8095>++ = *</color>p1<color:#ff8095>++</color>; <color:#ebd247>if</color>(<color:#ff8095>--</color>n1 <color:#ff8095>==</color> <color:#a980f5>0</color>) <color:#ebd247>break</color>;
    } <color:#ebd247>else</color> {
      <color:#ff8095>*</color>q<color:#ff8095>++ = *</color>p2<color:#ff8095>++</color>; <color:#ebd247>if</color>(<color:#ff8095>--</color>n2 <color:#ff8095>==</color> <color:#a980f5>0</color>) <color:#ebd247>break</color>;
    }
  }
  <color:#ebd247>while</color>(n1 <color:#ff8095><U+003E></color> <color:#a980f5>0</color>) {
    <color:#ff8095>*</color>q<color:#ff8095>++ = *</color>p1<color:#ff8095>++</color>; n1<color:#ff8095>--</color>;
  }
  <color:#ebd247>for</color>(<color:#ebd247>int</color> i <color:#ff8095>=</color> <color:#a980f5>0</color>; i <color:#ff8095><U+003C></color> n <color:#ff8095>-</color> n2; i<color:#ff8095>++</color>)
    a[i] <color:#ff8095>=</color> buf[i];

}
end title
@enduml
```

```plantuml
@startuml
<style>
root {
  margin 0
  padding 0
  backgroundColor #202020
}
title {
  horizontalAlignment left
  padding 0 0 4 6
  fontColor #e3e3e3
  fontStyle normal
  fontName monospaced
  fontSize 14
}
</style>
sprite TITLE <svg width="340" height="32">
<path d="M0 0 v18 a6 6 0 0 0 6 6 h298 a 6 6 0 0 0 6 -6 v-18" fill="#606060">
<text x="6" y="18" font-size="14" fill="white">merge4（ボトムアップ型・データ転送節約版）</text>
</svg>
title
<$TITLE>
<color:#ebd247>static  void</color>  <color:#8bdf4c>merge</color>(
  <color:#ebd247>int</color> <color:#ff8095>*</color>buf, <color:#ebd247>int</color> <color:#ff8095>*</color>a, <color:#ebd247>int</color> n1, <color:#ebd247>int</color> n2,
    COMPARE compare) {

  <color:#ebd247>int</color> <color:#ff8095>*</color>p1 <color:#ff8095>=</color> a;
  <color:#ebd247>int</color> <color:#ff8095>*</color>p2 <color:#ff8095>=</color> a <color:#ff8095>+</color> n1;
  <color:#ebd247>int</color> <color:#ff8095>*</color>q <color:#ff8095>=</color> buf;
  <color:#ebd247>for</color>(;;) {
    <color:#ebd247>if</color>(compare(<color:#ff8095>*</color>p1, <color:#ff8095>*</color>p2) <color:#ff8095><U+003C>=</color> <color:#a980f5>0</color>) {
      <color:#ff8095>*</color>q<color:#ff8095>++ = *</color>p1<color:#ff8095>++</color>; <color:#ebd247>if</color>(<color:#ff8095>--</color>n1 <color:#ff8095>==</color> <color:#a980f5>0</color>) <color:#ebd247>break</color>;
    } <color:#ebd247>else</color> {
      <color:#ff8095>*</color>q<color:#ff8095>++ = *</color>p2<color:#ff8095>++</color>; <color:#ebd247>if</color>(<color:#ff8095>--</color>n2 <color:#ff8095>==</color> <color:#a980f5>0</color>) <color:#ebd247>break</color>;
    }
  }
  <color:#ebd247>while</color>(n1 <color:#ff8095><U+003E></color> <color:#a980f5>0</color>) {
    <color:#ff8095>*</color>q<color:#ff8095>++ =</color> <color:#ff8095>*</color>p1<color:#ff8095>++</color>; n1<color:#ff8095>--</color>;
  }
  <color:#ebd247>while</color>(n2 <color:#ff8095><U+003E></color> <color:#a980f5>0</color>) {
    <color:#ff8095>*</color>q<color:#ff8095>++ =</color> <color:#ff8095>*</color>p2<color:#ff8095>++</color>; n2<color:#ff8095>--</color>;
  }
}
end title
@enduml
```
# 比較回数・転送回数の比較

試験条件は下記の通りである。

- 200,000,000 個の 32bit 整数を昇順ソートする。
- データの順序は以下の四種類である。
  - ゼロ（すべて同値）
  - 昇順：0 → 199,999,999
  - 降順：199,999,999 → 0
  - 乱数：0～199,999,999 の範囲で一様乱数（重複あり）
- 乱数発生器は XorShift である。
- 比較対象のソートアルゴリズムは以下の四つとする。
  - uCRT：クイックソート
  - glibc：再帰型マージソート
  - merge：非再帰型マージソート
  - merge4：非再帰型マージソート・データ転送節約版　※今回作成したもの

<table>
<caption>表１　比較回数の比較（単位は回）</caption>
<thead>
<tr><th>順序</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">merge4</th></th>
</thead>
<tbody>
<tr></tr>
<tr><th>ゼロ</th>
    <td style="text-align:right">399,999,999</td>
    <td style="text-align:right">2,728,894,208</td>
    <td style="text-align:right">2,804,304,128</td>
    <td style="text-align:right">2,804,304,128</td></tr>
<tr></tr>
<tr><th>昇順</th>
    <td style="text-align:right">5,363,792,412</td>
    <td style="text-align:right">2,728,894,208</td>
    <td style="text-align:right">2,804,304,128</td>
    <td style="text-align:right">2,804,304,128</td></tr>
<tr></tr>
<tr><th>降順</th>
    <td style="text-align:right">5,363,792,412</td>
    <td style="text-align:right">2,802,670,336</td>
    <td style="text-align:right">2,728,894,208</td>
    <td style="text-align:right">2,728,894,208</td></tr>
<tr></tr>
<tr><th>乱数</th>
    <td style="text-align:right">6,400,427,154</td>
    <td style="text-align:right">5,265,836,886</td>
    <td style="text-align:right">5,280,310,523</td>
    <td style="text-align:right">5,280,310,523</td></tr>
</tbody>
</table>

<table>
<caption>表２　転送回数の比較（単位は回）</caption>
<thead>
<tr><th>順序</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">merge4</th></th>
</thead>
<tbody>
<tr></tr>
<tr><th>ゼロ</th>
    <td style="text-align:right">0</td>
    <td style="text-align:right">5,457,788,416</td>
    <td style="text-align:right">5,408,608,256</td>
    <td style="text-align:right">5,600,000,000</td></tr>
<tr></tr>
<tr><th>昇順</th>
    <td style="text-align:right">265,782,274</td>
    <td style="text-align:right">5,457,788,416</td>
    <td style="text-align:right">5,408,608,256</td>
    <td style="text-align:right">5,600,000,000</td></tr>
<tr></tr>
<tr><th>降順</th>
    <td style="text-align:right">465,782,278</td>
    <td style="text-align:right">11,063,129,088</td>
    <td style="text-align:right">10,866,396,672</td>
    <td style="text-align:right">5,800,000,000</td></tr>
<tr></tr>
<tr><th>乱数</th>
    <td style="text-align:right">2,736,238,624</td>
    <td style="text-align:right">10,752,119,342</td>
    <td style="text-align:right">10,613,478,548</td>
    <td style="text-align:right">5,700,000,344</td></tr>
</tbody>
</table>

今回作成した merge4 について，比較回数は merge（非再帰型マージソート）と全く変わらない。一方，データ転送回数について，ゼロや昇順などソートする必要がないデータについては微増となっているが，降順と乱数についてはほぼ半減していることが分かる。これは実行時間に期待できそうだ。

<font color=#5B9BD5>■</font>uCRT，<font color=#ED7D31>■</font>glibc，<font color=#A5A5A5>■</font>merge，<font color=#997300>■</font>merge4

```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="M40 30 h280 v1 h-280">
<path d="M40 80 h280 v1 h-280">
<path d="M40 130 h280 v1 h-280">
<path d="M40 180 h280 v1 h-280">
<path d="M40 230 h280 v1 h-280">
<path d="M40 280 h280 v1 h-280">
<path d="M40 330 h280 v1 h-280">
</g>
<text x="25" y="336" font-size="16" fill="black">0</text>
<text x="15" y="286" font-size="16" fill="black">20</text>
<text x="15" y="236" font-size="16" fill="black">40</text>
<text x="15" y="186" font-size="16" fill="black">60</text>
<text x="15" y="136" font-size="16" fill="black">80</text>
<text x="5" y="86" font-size="16" fill="black">100</text>
<text x="5" y="36" font-size="16" fill="black">120</text>
<text x="40" y="24" font-size="16" fill="black">[億回]</text>
<text x="60" y="350" font-size="16" fill="black">ゼロ</text>
<text x="130" y="350" font-size="16" fill="black">昇順</text>
<text x="200" y="350" font-size="16" fill="black">降順</text>
<text x="270" y="350" font-size="16" fill="black">乱数</text>
<g fill="#5B9BD5">
<path d="M48 330 h12 v-17 h-12">
<path d="M118 330 h12 v-230 h-12">
<path d="M188 330 h12 v-230 h-12">
<path d="M258 330 h12 v-274 h-12">
</g>
<g fill="#ED7D31">
<path d="M62 330 h12 v-117 h-12">
<path d="M132 330 h12 v-117 h-12">
<path d="M202 330 h12 v-120 h-12">
<path d="M272 330 h12 v-226 h-12">
</g>
<g fill="#A5A5A5">
<path d="M76 330 h12 v-120 h-12">
<path d="M146 330 h12 v-120 h-12">
<path d="M216 330 h12 v-117 h-12">
<path d="M286 330 h12 v-226 h-12">
</g>
<g fill="#997300">
<path d="M90 330 h12 v-120 h-12">
<path d="M160 330 h12 v-120 h-12">
<path d="M230 330 h12 v-117 h-12">
<path d="M300 330 h12 v-226 h-12">
</g>
</svg>
title
<$FIGURE>
図１　比較回数の比較
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="M40 30 h280 v1 h-280">
<path d="M40 80 h280 v1 h-280">
<path d="M40 130 h280 v1 h-280">
<path d="M40 180 h280 v1 h-280">
<path d="M40 230 h280 v1 h-280">
<path d="M40 280 h280 v1 h-280">
<path d="M40 330 h280 v1 h-280">
</g>
<text x="25" y="336" font-size="16" fill="black">0</text>
<text x="15" y="286" font-size="16" fill="black">20</text>
<text x="15" y="236" font-size="16" fill="black">40</text>
<text x="15" y="186" font-size="16" fill="black">60</text>
<text x="15" y="136" font-size="16" fill="black">80</text>
<text x="5" y="86" font-size="16" fill="black">100</text>
<text x="5" y="36" font-size="16" fill="black">120</text>
<text x="40" y="24" font-size="16" fill="black">[億回]</text>
<text x="60" y="350" font-size="16" fill="black">ゼロ</text>
<text x="130" y="350" font-size="16" fill="black">昇順</text>
<text x="200" y="350" font-size="16" fill="black">降順</text>
<text x="270" y="350" font-size="16" fill="black">乱数</text>
<g fill="#5B9BD5">
<path d="M48 330 h12 v-0 h-12">
<path d="M118 330 h12 v-7 h-12">
<path d="M188 330 h12 v-12 h-12">
<path d="M258 330 h12 v-68 h-12">
</g>
<g fill="#ED7D31">
<path d="M62 330 h12 v-136 h-12">
<path d="M132 330 h12 v-136 h-12">
<path d="M202 330 h12 v-277 h-12">
<path d="M272 330 h12 v-269 h-12">
</g>
<g fill="#A5A5A5">
<path d="M76 330 h12 v-135 h-12">
<path d="M146 330 h12 v-135 h-12">
<path d="M216 330 h12 v-272 h-12">
<path d="M286 330 h12 v-265 h-12">
</g>
<g fill="#997300">
<path d="M90 330 h12 v-140 h-12">
<path d="M160 330 h12 v-140 h-12">
<path d="M230 330 h12 v-145 h-12">
<path d="M300 330 h12 v-143 h-12">
</g>
</svg>
title
<$FIGURE>
図２　転送回数の比較
end title
@enduml
```

# 実行時間の比較

試験条件を以下に示す。

- 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

試験結果を以下に示す。

<table>
<caption>表３　実行時間の比較（単位は秒）</caption>
<thead>
<tr><th>コンパイラ</th>
    <th>順序</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">merge4</th></th>
</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">3.796</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">3.797</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">3.752</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">17.495</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.984</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.961</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">2.927</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">18.346</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">3.729</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">3.415</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.393</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">17.146</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">2.259</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">2.262</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.240</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.296</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">2.971</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">2.973</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.643</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">16.481</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>
    <td style="text-align:right">2.049</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">2.046</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.074</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.010</td></tr>
</tbody>
</table>

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

<font color=#5B9BD5>■</font>uCRT，<font color=#ED7D31>■</font>glibc，<font color=#A5A5A5>■</font>merge，<font color=#997300>■</font>merge4

```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="M40 30 h280 v1 h-280">
<path d="M40 90 h280 v1 h-280">
<path d="M40 150 h280 v1 h-280">
<path d="M40 210 h280 v1 h-280">
<path d="M40 270 h280 v1 h-280">
<path d="M40 330 h280 v1 h-280">
</g>
<text x="25" y="336" font-size="16" fill="black">0</text>
<text x="25" y="276" font-size="16" fill="black">5</text>
<text x="15" y="216" font-size="16" fill="black">10</text>
<text x="15" y="156" font-size="16" fill="black">15</text>
<text x="15" y="96" font-size="16" fill="black">20</text>
<text x="15" y="36" font-size="16" fill="black">25</text>
<text x="40" y="24" font-size="16" fill="black">[秒]</text>
<text x="60" y="350" font-size="16" fill="black">ゼロ</text>
<text x="130" y="350" font-size="16" fill="black">昇順</text>
<text x="200" y="350" font-size="16" fill="black">降順</text>
<text x="270" y="350" font-size="16" fill="black">乱数</text>
<g fill="#5B9BD5">
<path d="M48 330 h12 v-1 h-12">
<path d="M118 330 h12 v-17 h-12">
<path d="M188 330 h12 v-18 h-12">
<path d="M258 330 h12 v-186 h-12">
</g>
<g fill="#ED7D31">
<path d="M62 330 h12 v-32 h-12">
<path d="M132 330 h12 v-32 h-12">
<path d="M202 330 h12 v-47 h-12">
<path d="M272 330 h12 v-216 h-12">
</g>
<g fill="#A5A5A5">
<path d="M76 330 h12 v-34 h-12">
<path d="M146 330 h12 v-34 h-12">
<path d="M216 330 h12 v-56 h-12">
<path d="M286 330 h12 v-233 h-12">
</g>
<g fill="#997300">
<path d="M90 330 h12 v-46 h-12">
<path d="M160 330 h12 v-46 h-12">
<path d="M230 330 h12 v-45 h-12">
<path d="M300 330 h12 v-210 h-12">
</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="M40 30 h280 v1 h-280">
<path d="M40 90 h280 v1 h-280">
<path d="M40 150 h280 v1 h-280">
<path d="M40 210 h280 v1 h-280">
<path d="M40 270 h280 v1 h-280">
<path d="M40 330 h280 v1 h-280">
</g>
<text x="25" y="336" font-size="16" fill="black">0</text>
<text x="25" y="276" font-size="16" fill="black">5</text>
<text x="15" y="216" font-size="16" fill="black">10</text>
<text x="15" y="156" font-size="16" fill="black">15</text>
<text x="15" y="96" font-size="16" fill="black">20</text>
<text x="15" y="36" font-size="16" fill="black">25</text>
<text x="40" y="24" font-size="16" fill="black">[秒]</text>
<text x="60" y="350" font-size="16" fill="black">ゼロ</text>
<text x="130" y="350" font-size="16" fill="black">昇順</text>
<text x="200" y="350" font-size="16" fill="black">降順</text>
<text x="270" y="350" font-size="16" fill="black">乱数</text>
<g fill="#5B9BD5">
<path d="M48 330 h12 v-1 h-12">
<path d="M118 330 h12 v-19 h-12">
<path d="M188 330 h12 v-19 h-12">
<path d="M258 330 h12 v-186 h-12">
</g>
<g fill="#ED7D31">
<path d="M62 330 h12 v-30 h-12">
<path d="M132 330 h12 v-30 h-12">
<path d="M202 330 h12 v-45 h-12">
<path d="M272 330 h12 v-254 h-12">
</g>
<g fill="#A5A5A5">
<path d="M76 330 h12 v-26 h-12">
<path d="M146 330 h12 v-26 h-12">
<path d="M216 330 h12 v-40 h-12">
<path d="M286 330 h12 v-241 h-12">
</g>
<g fill="#997300">
<path d="M90 330 h12 v-36 h-12">
<path d="M160 330 h12 v-36 h-12">
<path d="M230 330 h12 v-35 h-12">
<path d="M300 330 h12 v-220 h-12">
</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="M40 30 h280 v1 h-280">
<path d="M40 90 h280 v1 h-280">
<path d="M40 150 h280 v1 h-280">
<path d="M40 210 h280 v1 h-280">
<path d="M40 270 h280 v1 h-280">
<path d="M40 330 h280 v1 h-280">
</g>
<text x="25" y="336" font-size="16" fill="black">0</text>
<text x="25" y="276" font-size="16" fill="black">5</text>
<text x="15" y="216" font-size="16" fill="black">10</text>
<text x="15" y="156" font-size="16" fill="black">15</text>
<text x="15" y="96" font-size="16" fill="black">20</text>
<text x="15" y="36" font-size="16" fill="black">25</text>
<text x="40" y="24" font-size="16" fill="black">[秒]</text>
<text x="60" y="350" font-size="16" fill="black">ゼロ</text>
<text x="130" y="350" font-size="16" fill="black">昇順</text>
<text x="200" y="350" font-size="16" fill="black">降順</text>
<text x="270" y="350" font-size="16" fill="black">乱数</text>
<g fill="#5B9BD5">
<path d="M48 330 h12 v-1 h-12">
<path d="M118 330 h12 v-20 h-12">
<path d="M188 330 h12 v-20 h-12">
<path d="M258 330 h12 v-188 h-12">
</g>
<g fill="#ED7D31">
<path d="M62 330 h12 v-25 h-12">
<path d="M132 330 h12 v-25 h-12">
<path d="M202 330 h12 v-44 h-12">
<path d="M272 330 h12 v-198 h-12">
</g>
<g fill="#A5A5A5">
<path d="M76 330 h12 v-25 h-12">
<path d="M146 330 h12 v-25 h-12">
<path d="M216 330 h12 v-36 h-12">
<path d="M286 330 h12 v-192 h-12">
</g>
<g fill="#997300">
<path d="M90 330 h12 v-45 h-12">
<path d="M160 330 h12 v-41 h-12">
<path d="M230 330 h12 v-41 h-12">
<path d="M300 330 h12 v-206 h-12">
</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="M40 30 h280 v1 h-280">
<path d="M40 90 h280 v1 h-280">
<path d="M40 150 h280 v1 h-280">
<path d="M40 210 h280 v1 h-280">
<path d="M40 270 h280 v1 h-280">
<path d="M40 330 h280 v1 h-280">
</g>
<text x="25" y="336" font-size="16" fill="black">0</text>
<text x="25" y="276" font-size="16" fill="black">5</text>
<text x="15" y="216" font-size="16" fill="black">10</text>
<text x="15" y="156" font-size="16" fill="black">15</text>
<text x="15" y="96" font-size="16" fill="black">20</text>
<text x="15" y="36" font-size="16" fill="black">25</text>
<text x="40" y="24" font-size="16" fill="black">[秒]</text>
<text x="60" y="350" font-size="16" fill="black">ゼロ</text>
<text x="130" y="350" font-size="16" fill="black">昇順</text>
<text x="200" y="350" font-size="16" fill="black">降順</text>
<text x="270" y="350" font-size="16" fill="black">乱数</text>
<g fill="#5B9BD5">
<path d="M48 330 h12 v-1 h-12">
<path d="M118 330 h12 v-18 h-12">
<path d="M188 330 h12 v-18 h-12">
<path d="M258 330 h12 v-189 h-12">
</g>
<g fill="#ED7D31">
<path d="M62 330 h12 v-23 h-12">
<path d="M132 330 h12 v-24 h-12">
<path d="M202 330 h12 v-35 h-12">
<path d="M272 330 h12 v-192 h-12">
</g>
<g fill="#A5A5A5">
<path d="M76 330 h12 v-20 h-12">
<path d="M146 330 h12 v-20 h-12">
<path d="M216 330 h12 v-29 h-12">
<path d="M286 330 h12 v-190 h-12">
</g>
<g fill="#997300">
<path d="M90 330 h12 v-27 h-12">
<path d="M160 330 h12 v-27 h-12">
<path d="M230 330 h12 v-27 h-12">
<path d="M300 330 h12 v-184 h-12">
</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="M40 30 h280 v1 h-280">
<path d="M40 90 h280 v1 h-280">
<path d="M40 150 h280 v1 h-280">
<path d="M40 210 h280 v1 h-280">
<path d="M40 270 h280 v1 h-280">
<path d="M40 330 h280 v1 h-280">
</g>
<text x="25" y="336" font-size="16" fill="black">0</text>
<text x="25" y="276" font-size="16" fill="black">5</text>
<text x="15" y="216" font-size="16" fill="black">10</text>
<text x="15" y="156" font-size="16" fill="black">15</text>
<text x="15" y="96" font-size="16" fill="black">20</text>
<text x="15" y="36" font-size="16" fill="black">25</text>
<text x="40" y="24" font-size="16" fill="black">[秒]</text>
<text x="60" y="350" font-size="16" fill="black">ゼロ</text>
<text x="130" y="350" font-size="16" fill="black">昇順</text>
<text x="200" y="350" font-size="16" fill="black">降順</text>
<text x="270" y="350" font-size="16" fill="black">乱数</text>
<g fill="#5B9BD5">
<path d="M48 330 h12 v-1 h-12">
<path d="M118 330 h12 v-19 h-12">
<path d="M188 330 h12 v-20 h-12">
<path d="M258 330 h12 v-205 h-12">
</g>
<g fill="#ED7D31">
<path d="M62 330 h12 v-30 h-12">
<path d="M132 330 h12 v-30 h-12">
<path d="M202 330 h12 v-40 h-12">
<path d="M272 330 h12 v-214 h-12">
</g>
<g fill="#A5A5A5">
<path d="M76 330 h12 v-24 h-12">
<path d="M146 330 h12 v-25 h-12">
<path d="M216 330 h12 v-35 h-12">
<path d="M286 330 h12 v-213 h-12">
</g>
<g fill="#997300">
<path d="M90 330 h12 v-36 h-12">
<path d="M160 330 h12 v-36 h-12">
<path d="M230 330 h12 v-32 h-12">
<path d="M300 330 h12 v-198 h-12">
</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="M40 30 h280 v1 h-280">
<path d="M40 90 h280 v1 h-280">
<path d="M40 150 h280 v1 h-280">
<path d="M40 210 h280 v1 h-280">
<path d="M40 270 h280 v1 h-280">
<path d="M40 330 h280 v1 h-280">
</g>
<text x="25" y="336" font-size="16" fill="black">0</text>
<text x="25" y="276" font-size="16" fill="black">5</text>
<text x="15" y="216" font-size="16" fill="black">10</text>
<text x="15" y="156" font-size="16" fill="black">15</text>
<text x="15" y="96" font-size="16" fill="black">20</text>
<text x="15" y="36" font-size="16" fill="black">25</text>
<text x="40" y="24" font-size="16" fill="black">[秒]</text>
<text x="60" y="350" font-size="16" fill="black">ゼロ</text>
<text x="130" y="350" font-size="16" fill="black">昇順</text>
<text x="200" y="350" font-size="16" fill="black">降順</text>
<text x="270" y="350" font-size="16" fill="black">乱数</text>
<g fill="#5B9BD5">
<path d="M48 330 h12 v-1 h-12">
<path d="M118 330 h12 v-16 h-12">
<path d="M188 330 h12 v-18 h-12">
<path d="M258 330 h12 v-199 h-12">
</g>
<g fill="#ED7D31">
<path d="M62 330 h12 v-22 h-12">
<path d="M132 330 h12 v-22 h-12">
<path d="M202 330 h12 v-30 h-12">
<path d="M272 330 h12 v-192 h-12">
</g>
<g fill="#A5A5A5">
<path d="M76 330 h12 v-19 h-12">
<path d="M146 330 h12 v-19 h-12">
<path d="M216 330 h12 v-29 h-12">
<path d="M286 330 h12 v-188 h-12">
</g>
<g fill="#997300">
<path d="M90 330 h12 v-25 h-12">
<path d="M160 330 h12 v-25 h-12">
<path d="M230 330 h12 v-25 h-12">
<path d="M300 330 h12 v-180 h-12">
</g>
</svg>
title
<$FIGURE>
図８　intel icx-cl 64bit版
end title
@enduml
```

# 結論

- 配列のデータが全てゼロや昇順のようなソート済みの特殊データについては比較回数・転送回数ともにほとんど変わらないにも関わらず，実行時間は微増となっている。

- 降順や乱数のようにデータを入れ替える必要があるものについては，ほとんどのコンパイラで（LLVM clang-cl 32bit 版を除いて）高速化を実現できている。

- LLVM clang-cl 32bit 版でパフォーマンスが上がらなかった点については謎である。おそらくループアンローリングや関数のインライン展開などの最適化を積極的に行ったが，汎用レジスタの少ない x86 アーキテクチャでは逆効果だったと推察している。