1要素になるまで分割し、整列済みの列の先頭を比較しながらマージします。一時配列tmpに結果を集めてから元の配列へ戻します。

再帰的な分割と一時配列へのマージを示すシミュレーター

再生・ステップ実行・スライダーで操作できます。下段は一時配列tmpです。

最良O(n log n)

平均O(n log n)

最悪O(n log n)

追加領域O(n)

安定はい

入力順序の影響最悪でも性能を維持

先頭同士を比較してマージする

両側とも整列済みなので、先頭の小さい方が全体の次の最小値です。マージは両側の長さの合計に比例する時間で完了します。O(log n)階層の各段でO(n)の処理をするため、最悪でもO(n log n)です。

同じ値なら左を先に選ぶ（a[i] <= a[j]）ことで安定性を保ちます。比較を <にすると、この性質が失われます。

演習：転倒数を数える

右の値が小さいとき、左側の残りすべてがその値より大きくなります。その時点でmid − i + 1を転倒数に加えると、全体をO(n log n)で計算できます。

else:                       # 右の値が小さい
    inv += mid - i + 1      # 左の残りはすべてa[j]より大きい
    tmp.append(a[j]); j += 1