差分

配列を短く分割し、徐々に併合していくことでソートを行う。

[[キャラソート]]でも採用されているらしい<ref>http://marineturtle.sakura.ne.jp/script/sort/hpsort/mergesort_exp.html</ref>。

<source lang="haskell">

mergeinternal [] [] = []