はじめに ソートのアルゴリズムは通常、実数における通常の順序関係のように全順序である順序関係に対して行うものですが、本記事では半順序に対するソートのアルゴリズムについて解説します。 半順序とは 集合X上の二項関係 ≦ が半順序であるとは、以下の性質を満たすものとして定義されます。 反射律 任意のx $\in$ Xに対し、x ≦ x を満たす。 反対称律 任意のx, y $\in$ Xに対し、x ≦ y かつ y ≦ x ならば x = yを満たす。 推移律 任意のx, y, z $\in$ Xに対し、x ≦ y かつ y ≦ z ならば x ≦ zを満たす。 ここに全順序律 任意のx, y $\in$ Xに対し、x ≦ y または y ≦ x を満たすこと追加したものを全順序と言います。 通常、ソートを行うアルゴリズムはこの全順序関係を仮定した上で成り立つアルゴリズムです。しかし以下のよう