論文843 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/843 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。
本文はサイトの記事でも読めます（2026年10月4日 13:50 に公開します）。
日付の証拠（OpenTimestamps）：日本語版の .ots・英語版の .ots・SHA256SUMS
予備の置き場所（ミラー。中身は上と同じです）：PDF 日本語・PDF English・SHA256SUMS
住所：https://www.yamagishiyuuki.com/yoi/843・CC BY 4.0・プレプリント（査読を経ていません）・ORCID 0009-0006-8587-3450
引用するとき
山岸勇輝 (2026). 比べる回数の下界は、入力ではなく答えの通り数で決まる [論文843]. YOI: https://www.yamagishiyuuki.com/yoi/843
Yamagishi, Y. (2026). The Lower Bound on Comparisons Comes From the Number of Answers, Not From the Input [Paper 843]. YOI: https://www.yamagishiyuuki.com/yoi/843
@misc{yamagishi2026yoi843,
author = {Yamagishi, Yuuki},
title = {The Lower Bound on Comparisons Comes From the Number of Answers, Not From the Input},
year = {2026},
howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/843},
note = {Preprint, edition 1}
}
指紋（SHA-256）と確かめ方
c7dd4c777b98cdb5904c1901d55b6bbf6218b356959556ac849031e0ee6b9931 yamagishi_yoi843_v1_jp.pdf475588b1f1b804717ca77c56509d93d2f66456bf62c646cb8b6becf51c404af2 yamagishi_yoi843_v1_en.pdfPDF と .ots を同じ場所に保存し、opentimestamps.org に .ots、続けて PDF を落とすと、記録された日時が表示されます。PDF が 1 バイトでも変わっていれば通りません。
日付の証拠（OpenTimestamps）
2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969440・969456・969461 に記録されました（2026年10月01日 19:28（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。
書誌
| 題名 | 比べる回数の下界は、入力ではなく答えの通り数で決まる |
|---|---|
| Title | The Lower Bound on Comparisons Comes From the Number of Answers, Not From the Input |
| 著者 | 山岸 勇輝 (Yuuki YAMAGISHI)・ORCID 0009-0006-8587-3450 |
| 所属 | 山岸複雑性トーラス研究所 (Yamagishi Complexity Torus Lab, Japan) |
| 版 | 第1版（2026年9月） |
| 言語 | 日本語・英語 |
| 種別 | プレプリント（査読を経ていません） |
| ライセンス | CC BY 4.0（出典を示せば、複製・再配布・改変ができます） |
| YOI | https://www.yamagishiyuuki.com/yoi/843 |
要旨
「この並べ方は速い」と言うとき、何と比べているのかがずれていることがある。本稿は、下界がどこから来るのかを数える。新しい定理も法則も主張しない。
第一に、下界は答えの通り数の対数である。$n=8$ では $\log_2 8!=15.2992$、切り上げて $16$ 回である（第2節）。
第二に、実際の手順はそれに近づく。二分挿入とマージは $n=8$ でどちらも最悪 $17$ 回、下界との差は $1$ 回しかない（第2節）。
第三に、手順によっては遠い。挿入ソートは最悪 $28$ 回で、下界の $1.75$ 倍である（第2節）。
第四に、平均も下界を割らない。二分挿入の平均は $\mathbf{15.5905}$ 回で、$\log_2 8!=15.2992$ を上回る（第2節）。
第五に、これが本稿の芯である。ある入力なら下界を割れる。すでに並んだ $8$ 個を挿入ソートに入れると $7$ 回で済み、下界 $16$ を大きく下回る（第3節）。
第六に、分離子は、ある入力での回数を問うか、どの入力でも足りる回数を問うかである。下界が守っているのは後者だけである（第4節）。
キーワード：比較ソート、下界、決定木、最悪と平均、全数え上げ、模型
Abstract
When something is called “fast”, the comparison being made is often not the one intended.This paper counts where the lower bound comes from.No new theorem or law is claimed.
First, the bound is the logarithm of the number of answers: for $n=8$ it is $\log_2 8!=15.2992$, rounded up to $16$ (Section 2).
Second, real procedures come close to it: binary insertion and merge sort both take $17$ in the worst case at $n=8$, one above the bound (Section 2).
Third, others stay far from it: insertion sort takes $28$, which is $1.75$ times the bound (Section 2).
Fourth, the averages do not fall below it either: binary insertion averages $\mathbf{15.5905}$, above $\log_2 8!=15.2992$ (Section 2).
Fifth, and this is the core. On one input the bound can be beaten: eight already-sorted items take insertion sort $7$ comparisons, far below $16$ (Section 3).
Sixth, the separator is whether one asks about the count on one input or the count that suffices for every input: the bound protects only the second (Section 4).
Keywords: comparison sort, lower bound, decision tree, worst and average case, exhaustive enumeration, model
版の記録
ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/843/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/843 はいつも最新の版を指します）。