<和演算> 入力 : A [(as0, ae0), (as1, ae1), (as2, ae2), ...] B [(bs0, be0), (bs1, be1), (bs2, be2), ...] C [空] 結果 : C [(cs0, ce0), (cs1, ce1), (cs2, ce2), ...]
計算 : <1> A と B の全要素を先端インデックスの昇順でひとつのリスト X に並べる <2> X から先頭要素 (xsi, xei) を切り出して C の後尾要素の後ろに追加する <3> X の先頭要素 (xsj, xej) を切り出し、C の後尾要素 (csi, cei) と比較する if cei < xsj then C の後尾要素の後ろに (xsj, xej) を追加する else (csi, cei) を (min (csi, xsi), max (cej, xej)) に変更する <4> X の要素が残っていれば <3> へ
X を作りたくなければ、ループの各ステップにおいて A B の先頭要素の 先端インデックスが小さい方を選んで (xsj, xej) とすればいい。
