LoginSignup
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@TETSURO1999

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

Last updated at Posted at 2025-04-27

はじめに

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

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

  • qsort_glibc() は普通に再帰関数として作成しているが，qsort_ucrt() は再帰関数ではなくループ処理で済ませており，再帰関数の呼び出しオーバーヘッドを減らすなど細かい工夫が施されている。

  • qsort_glibc() は配列の要素数が 2 個になってもマージソートを行っているが，qsort_ucrt() は分割された配列の要素数が 8 個以下になると選択ソートに切り替えるなど細かい工夫が施されている。

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

基本的なアイディア

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

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

ボトムアップ型の課題

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

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

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

ソースコード全容

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

ボトムアップ型マージソート関数
/* 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 で用いたものと全く同じである。

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

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

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

ソート関数本体の冒頭部分
/* 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行は終端処理である。

/* 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 個の要素が余った場合，コピー処理を省略するなどの工夫が施されている。

/* 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：非再帰型マージソート　※今回作成したもの
表１　バイナリサイズの比較（単位はバイト）
コンパイラ uCRT glibc merge
Visual C++ 32bit 118,272 117,760 118,272
64bit 142,848 142,848 142,848
LLVM clang-cl 32bit 118,784 118,784 119,296
64bit 148,480 148,480 148,992
intel icx-cl 32bit 166,400 169,472 169,984
64bit 208,384 226,304 227,328

実行時間の比較

実行時間の比較を以下に示す。

表２　実行時間の比較（単位は秒）
コンパイラ 条件 uCRT glibc merge
Visual C++
32bit版		 ゼロ 0.090 2.660 2.835
昇順 1.433 2.656 2.848
降順 1.475 3.914 4.668
乱数 15.505 17.996 19.431
Visual C++
64bit版		 ゼロ 0.093 2.470 2.158
昇順 1.582 2.473 2.148
降順 1.617 3.769 3.370
乱数 15.500 21.129 20.050
LLVM clang-cl
32bit版		 ゼロ 0.098 2.066 2.095
昇順 1.627 2.060 2.109
降順 1.688 3.642 3.015
乱数 15.636 16.487 15.981
LLVM clang-cl
64bit版		 ゼロ 0.089 1.958 1.679
昇順 1.460 1.997 1.663
降順 1.523 2.942 2.456
乱数 15.710 16.022 15.853
intel icx-cl
32bit版		 ゼロ 0.070 2.488 2.038
昇順 1.592 2.498 2.050
降順 1.691 3.333 2.877
乱数 17.120 17.809 17.767
intel icx-cl
64bit版		 ゼロ 0.064 1.811 1.621
昇順 1.366 1.797 1.608
降順 1.491 2.507 2.418
乱数 16.584 15.969 15.682

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

■uCRT，■glibc，■merge

結論

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

次回

次回に続く。

  1. 再帰なしのマージソート - WordPress ↩

  2. 再帰なしでマージソートやってみたら驚くほど高速化した話 - HatenaBlog ↩

  3. アルゴリズムとデータ構造編【整列アルゴリズム】 第７章 - Programming Place Plus ↩

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?