マージソート

取る側を決める比較を <= から < に変えると、同じ値のとき右が先に出ます。安定かどうかは等号 1 文字で決まります。