マージソート(SQLite)
アルゴリズムの名前が分からないのですが、途中でマージは使われているのでマージソートの一種でしょうか。ぼくが見ているSQLiteのままのコード(pcache.cの457行目-のpcacheMergeDirtyListがmergeに、pcacheSortDirtyListがsortに対応します)だと一緒にすると失敗するので調節しました。SQLiteの中では2^(N_SORT_BUCKET-1)(N_SORT_BUCKET=32)までの数のページを扱えることになっているのですが、そんな状況考えられないのでSQLITEの方にバグがあるとしても、バグに出会うことは無いでしょう。
インプットのリストの長さが2^(N_SORT_BUCKET-1)になるまではsort(inp)関数の中のa[N_SORT_BUCKET]はs(n)をn要素をソートしたリストを表すことにすると、a[0]=s(1), a[1]=s(2), a[2]=s(4),..a[i]=s(2^i)になっていることがわかります。試しにa[k+1]に値が入る瞬間をかんがえてみると、a[0]-a[k]が埋まった状態で再びwhileステートメントの一番上に来ます。a[0]はNoneではないのでp=sort(2)が入ります、次にp=s(s(2),s(2))=s(4), p = s(s(4), s(4)) = s(8)...と変化していきます。要するにi=kのときpにはa[0]-a[i]までが含む、全ての要素をソートしたものが入り、i=k+1のときにa[k+1]=pになってbreakします。このときpのsortした要素の数は1+sum_{i=0}^{k}2^{i}=2^{k+1}です。だからa[k+1]=s(2^{k+1})というわけです。
#!/usr/bin/env python2.6 import unittest import random import heapq def merge_sort(a, b): if a is None: return b elif b is None: return a return [i for i in heapq.merge(a, b)] N_SORT_BUCKET = 6 def sort(inp): a = [None] * N_SORT_BUCKET is_reached = False while len(inp): p = [inp.pop()] for i in range(N_SORT_BUCKET): if a[i] is None: a[i] = p break else: p = merge_sort(a[i], p) a[i] = None if i == N_SORT_BUCKET-1: """ To get here, there need to be 2^(N_SORT_BUCKET-1) elements in the input list. """ a[i] = p is_reached = True p = a[0] for i in range(1, N_SORT_BUCKET): p = merge_sort(p, a[i]) return p, is_reached return range(20) class SortTests(unittest.TestCase): def test_merge_sort(self): ia = [i*2 for i in range(5)] ib = [i*2+1 for i in range(5)] self.assertEqual(range(10), merge_sort(ia, ib)) def test_sort(self): for i in range(1, N_SORT_BUCKET-1): inp = range(1<<i) random.shuffle(inp) self.assertEqual((range(1<<i), False), sort(inp)) inp = range(1<<(N_SORT_BUCKET-1)) random.shuffle(inp) self.assertEqual((range(1<<(N_SORT_BUCKET-1)), True), sort(inp)) if __name__ == '__main__': unittest.main()