ところで突然マージソートのプログラムを書くことになった. マージソート に関しては大体のことは理解している心算りであったが, TAOCPの5.2.4項 を眺めたら, 意外と巧妙なことをやっているらしい. しかし, TAOCPのプ ログラムは例によって自然言語で書いてあり, 読む気にもならない. 私と しては, 再帰プログラムでさっさと書けるのではないかと思い立ち, やっ てみたのがこのブログである.
とりさえずマージソートの核心部分のおさらいから. 下の図にはA, B, Cの 3つの図がある, 似たような絵はTAOCPにあり, データの数値もそこから 借用した.
その手順の最初が図Bで, 最後が図Cである. まずBから. 上の列が与えられた ソートすべきデータ列である. 下の列は部分的にマージされた列で, 元の数列と同じ 長さの領域を別に用意する.
マージされる2つの数列は, 上の数列の両端から, s0とs1で示すように内側に向って 段々大きくなるように並んでいると考える. ソートされた列の終は次の数値が今の数値より小さく なるところである. 図では縦線で示した. 上の数列の左からをs0, 右からをs1とし, これをマージして用意した領域の左からt0として詰める.
s0とs1とでt0が出来たら, 続いてs0の内側のs2と, s1の内側のs3をマージし, t0を作った領域の, 今度は右端からt1として詰めていく. こうして行くとそのうち, 比べる べき数が同じ場所になり, tの領域も中程に1個所, 空地が残った状態になり, その残った数を空地に移すとこの回のマージは終了する.
次はこうして得られたtの数列を出発側にし, また同じようなマージを繰り返す. その 内, 図Cのように, 同じ数(この図では中程の908)を比べる状態になり, tの 領域の唯一の空地が右端に残り, そこに908を移動してソートは終了する.
後はこれを正直にプログラムにすることだ. Schemeで書いたのがこれである. 関数名がalgorithm524nなのは, TAOCPのAlgorithm524Nを書き換えたから である. 引数のrはソートすべき数列.
すぐにtwowaymergesortというサブルーチンがある. これは図BやCの1回のsからtへの マージである. 引数のrsはs(source)の数列. その長さがnで, その長さのt(target)の 数列の場所. Schemeではリストの要素を取るのに, list-refのように長い関数名を 書かなくてはならないので, 数列rsの添字iを取り出す関数rや, sのi番目をtのl 番目に移動するmoveなど, よく使う関数(手続き)を用意する. (MIT Scheme にはどういう訳かlist-set!がないので, 自分で定義して使っている.)
let文は次に使うsの左の場所の添字i, 右の添字j, tの左の添字k, 右の添字lを 初期化する.
次にtoleftとtorightがあるが, 新しい領域の左にあるtへ移すか右にあるtの 移すかで使い分ける. その夫々にfromleftとfromrightがある. これは 比較の一方が空になった後, もう一方の残りをどちらのsから移動するか で使い分ける.
(define (algorithm524n r)
(define (twowaymergesort rs)
(let* ((n (length rs))(rt (make-list n '())))
(define (r i) (list-ref rs i))
(define (move l i) (list-set! rt l (r i)))
(define (less? a b) (let ((rsa (r a)) (rsb (r b)))
(< rsa rsb)))
(let ((i 0) (j (- n 1)) (k 0) (l (- n 1)))
(define (toleft)
(define (fromright)
(move k j)(set! j (- j 1))(set! k (+ k 1))
(if (less? j (+ j 1))(toright)(fromright)))
(define (fromleft)
(move k i)(set! i (+ i 1))(set! k (+ k 1))
(if (less? (- i 1) i)(fromleft)(toright)))
(if (= i j) (begin (move k i)
(if (< k (- n 1))(twowaymergesort rt) rt))
(if (less? i j)
(begin (move k i)
(set! i (+ i 1)) (set! k (+ k 1))
(if (less? (- i 1) i)
(toleft) (fromright)))
(begin (move k j)
(set! j (- j 1)) (set! k (+ k 1))
(if (less? j (+ j 1))
(fromleft) (toleft))))))
(define (toright)
(define (fromright)
(move l j)(set! j (- j 1))(set! l (- l 1))
(if (less? j (+ j 1))(toleft)(fromright)))
(define (fromleft)
(move l i)(set! i (+ i 1))(set! l (- l 1))
(if (less? (- i 1) i)(fromleft)(toleft)))
(if (= i j) (begin (move l i)
(twowaymergesort rt))
(if (less? i j)
(begin (move l i)
(set! i (+ i 1)) (set! l (- l 1))
(if (less? (- i 1) i)
(toright) (fromright)))
(begin (move l j)
(set! j (- j 1)) (set! l (- l 1))
(if (less? j (+ j 1))
(fromleft) (toright))))))
(toleft))))
(twowaymergesort r))
(algorithm524n
'(503 87 512 61 908 170 897 275
653 426 154 509 612 677 765 703))
TAOCPには, merge sortは1945年頃, John von Neumannが提案したと
書いてある.
