Python bisect.insort()の使い方｜insortの意味・left/rightの違い・key引数と計算量
bisect.insort()は、ソート済みのリストに、並び順を崩さない位置へ値を挿入する関数です。insortは「insert in sorted order（並び順どおりに挿入する）」の意味で、bisect.insort(リスト, 値)と書くとリストがその場で書き換わり、戻り値はNoneです。
この記事では、insort()の基本、insort_leftとinsort_rightの違い、Python 3.10で入ったkey引数、計算量の誤解、append＋sortとの速度比較を、Python 3.12で実行した結果つきで説明します。
insortの意味とbisect.insort()の基本
Python公式ドキュメントでは、insort_left()は「x を a にソート順で挿入する」関数と説明されています。insort()はinsort_right()の別名です（bisect — Array bisection algorithm、2026年10月18日確認）。
import bisect
b = [10, 20, 30]
bisect.insort(b, 25)
bisect.insort(b, 5)
bisect.insort(b, 20)
print(b)
print(bisect.insort(b, 15))
print(b)実行結果：
[5, 10, 20, 20, 25, 30]
None
[5, 10, 15, 20, 20, 25, 30]どこに入れるかを自分で計算しなくても、並び順が保たれます。list.sort()と同じく戻り値はNoneなので、b = bisect.insort(b, 15)と書くとbがNoneになります。
| 関数 | 同じ値があるとき | 中身 |
|---|---|---|
insort(a, x) |
既存の値の後ろに入れる | insort_rightと同じ |
insort_right(a, x) |
既存の値の後ろに入れる | bisect_rightで位置を探してinsert |
insort_left(a, x) |
既存の値の前に入れる | bisect_leftで位置を探してinsert |
シグネチャはどれも(a, x, lo=0, hi=len(a), *, key=None)です。loとhiで探す範囲を絞れますが、普段は指定しません。位置だけを知りたいときのbisect_left／bisect_rightは「Python bisect_leftとbisect_rightの違い」で解説しています。
insort_leftとinsort_rightの違いが出る例
数値だけのリストでは、同じ値を前に入れても後ろに入れても見た目は変わりません。違いが見えるのは、比較に使う部分は同じで、ほかの情報が違う要素を入れるときです。keyで1番目の数字だけを比べるようにして試します（Python 3.10以降）。
import bisect
e = [(1, "A"), (2, "B"), (3, "D")]
bisect.insort_left(e, (2, "Z"), key=lambda t: t[0])
print("left :", e)
e = [(1, "A"), (2, "B"), (3, "D")]
bisect.insort_right(e, (2, "Z"), key=lambda t: t[0])
print("right:", e)実行結果：
left : [(1, 'A'), (2, 'Z'), (2, 'B'), (3, 'D')]
right: [(1, 'A'), (2, 'B'), (2, 'Z'), (3, 'D')]同じ2でも、leftは既存の(2, 'B')の前、rightは後ろに入りました。「同じ値なら先に来たものを前に置きたい（到着順を保ちたい）」ならinsort（right）を使います。
key引数でタプル・辞書を挿入する（Python 3.10以降）
keyを付けないと、タプルは2番目以降の要素まで比べられます。
e = [(1, "A"), (2, "B"), (3, "D")]
bisect.insort(e, (2, "A"))
print(e)実行結果：
[(1, 'A'), (2, 'A'), (2, 'B'), (3, 'D')]辞書はそもそも大小比較ができないので、keyが必須です。
users = [{"name": "A", "age": 20}, {"name": "C", "age": 40}]
bisect.insort(users, {"name": "B", "age": 30}, key=lambda u: u["age"])
print([u["name"] for u in users])
try:
bisect.insort(users, {"name": "D", "age": 35})
except TypeError as ex:
print("TypeError:", ex)実行結果：
['A', 'B', 'C']
TypeError: '<' not supported between instances of 'dict' and 'dict'注意点が1つあります。公式ドキュメントにあるとおり、insortのkeyは挿入する値xにも適用されます（bisect_leftなどの探索関数とは扱いが違います）。そのためxにはキーではなく、リストの要素と同じ形（上の例なら辞書そのもの）を渡します。
keyはPython 3.10で追加されました。3.9以前で渡すとエラーになります（macOS標準のPython 3.9.6で確認）。
TypeError: 'key' is an invalid keyword argument for insort_right()降順のリストにinsortするとおかしくなる
bisectは昇順に並んでいることを前提にしています。降順のリストにそのまま使うと、エラーは出ずに間違った位置に入ります。
d = [30, 20, 10]
bisect.insort(d, 25)
print(d)
d = [30, 20, 10]
bisect.insort(d, 25, key=lambda v: -v) # 符号を反転したキーで昇順として扱う
print(d)実行結果：
[30, 20, 10, 25]
[30, 25, 20, 10]数値の降順なら、key=lambda v: -vで正しく入ります。そもそも並んでいないリストでも同じで、[30, 10, 20]に15を入れると[30, 10, 15, 20]になります。bisectはソート済みかどうかを確認しないので、最初に1回ソートし、以降はinsortだけで足すというルールを守ってください。
insortの計算量：探すのはO(log n)、挿入はO(n)
「二分探索だから速い」と思われがちですが、公式ドキュメントには「O(log n)の探索より、遅いO(n)の挿入のほうが支配的」と書かれています。リストの途中に入れると、それより後ろの要素をすべて1つずつずらす必要があるためです。
import bisect, time
for n in [10_000, 100_000, 1_000_000]:
a = list(range(n))
s = time.perf_counter()
for _ in range(1000):
bisect.insort(a, -1) # 毎回先頭に入る（最悪ケース）
head = (time.perf_counter() - s) * 1000
b = list(range(n))
s = time.perf_counter()
for _ in range(1000):
bisect.insort(b, n + 1) # 毎回末尾に入る
tail = (time.perf_counter() - s) * 1000
print(f"n={n:>9,} 先頭へ1000回: {head:7.2f} ms 末尾へ1000回: {tail:5.2f} ms")実行結果（Apple M2、Python 3.12）：
n= 10,000 先頭へ1000回: 1.78 ms 末尾へ1000回: 0.14 ms
n= 100,000 先頭へ1000回: 19.70 ms 末尾へ1000回: 0.14 ms
n=1,000,000 先頭へ1000回: 161.29 ms 末尾へ1000回: 0.16 ms先頭への挿入は要素数にほぼ比例して遅くなり、末尾への挿入はほとんど変わりません。差を生んでいるのは探索ではなく、要素をずらす処理です。
append＋sortとの速度比較
では「1件足すたびにappendしてsortし直す」書き方と比べるとどうでしょうか。ランダムな値2万件を1件ずつ追加しました。
import bisect, random, time
random.seed(0)
data = [random.random() for _ in range(20000)]
def t(f):
s = time.perf_counter(); f(); return (time.perf_counter() - s) * 1000
def by_insort():
a = []
for x in data:
bisect.insort(a, x)
def by_append_sort_each():
a = []
for x in data:
a.append(x)
a.sort()
def by_sort_once():
a = []
for x in data:
a.append(x)
a.sort()
print(f"insortで1件ずつ : {t(by_insort):7.1f} ms")
print(f"append+sortを毎回 : {t(by_append_sort_each):7.1f} ms")
print(f"最後に1回だけsort : {t(by_sort_once):7.1f} ms")実行結果（Apple M2、Python 3.12。数値は実行ごとに多少変わります）：
insortで1件ずつ : 20.1 ms
append+sortを毎回 : 431.9 ms
最後に1回だけsort : 1.8 ms| 状況 | 選ぶもの |
|---|---|
| 全部集めてから1回だけ並べればよい | appendして最後にsort()（いちばん速い） |
| 追加のたびにソート済みの状態が必要 | insort（毎回sort()より大幅に速い） |
| 挿入と検索を交互に繰り返す | insort＋bisect_left |
| 最小値（上位N件）だけを何度も取り出す | heapq |
| 件数がとても多く、挿入も頻繁 | リスト以外のデータ構造を検討 |
処理時間の測り方は「Python timeit.timeit()の使い方」も参考にしてください。
insortの使用例：スコアを順位表に追加する
import bisect
ranking = [] # (点数, 名前) を点数の昇順で保持
for name, score in [("佐藤", 72), ("鈴木", 88), ("高橋", 65), ("田中", 88)]:
bisect.insort(ranking, (score, name), key=lambda r: r[0])
for score, name in reversed(ranking):
print(score, name)実行結果：
88 田中
88 鈴木
72 佐藤
65 高橋同点の場合、insort（right）は後から来た田中を鈴木の後ろに入れ、表示時にreversedで逆順にしているため田中が先に出ています。同点は先着順で表示したいなら、insort_leftに変えると鈴木が先になります。
よくある質問
Q. insortとはどういう意味ですか？
insert in sorted order、つまり「並び順どおりに挿入する」という意味です。Pythonではbisectモジュールの関数名で、ソート済みリストの正しい位置に値を入れます。
Q. bisect.insort()の戻り値は何ですか？
Noneです。リストそのものが書き換わるので、戻り値を代入せずにそのままリストを使います。
Q. insortとinsort_rightの違いは何ですか？
違いはありません。insortはinsort_rightの別名で、同じ値がすでにあるときはその後ろに挿入します。前に入れたいときはinsort_leftを使います。
Q. insortの計算量はO(log n)ですか？
位置を探す部分はO(log n)ですが、リストへの挿入がO(n)なので、全体ではO(n)です。それでも毎回sort()し直すよりは速く済みます。
まとめ
bisect.insort(a, x)はソート済みリストの正しい位置に挿入する。戻り値はNoneinsortはinsort_rightと同じ。同じ値の前に入れるならinsort_leftkey引数はPython 3.10以降。xにもkeyが適用されるので要素そのものを渡す- 昇順が前提。降順なら
key=lambda v: -v - 探索はO(log n)でも挿入はO(n)。まとめて並べるなら最後に1回
sort()が速い
