概要
概要
大きい問題を半分ずつの小さい問題に分けて進める方法です。半分ずつ整列して、最後に 2 つの整列済み配列をまとめます。
ソート / Merge Sort（マージソート）
大きい問題を半分ずつの小さい問題に分けて進める方法です。半分ずつ整列して、最後に 2 つの整列済み配列をまとめます。
目次
このページでわかること
概要
大きい問題を半分ずつの小さい問題に分けて進める方法です。半分ずつ整列して、最後に 2 つの整列済み配列をまとめます。
考え方
配列を半分ずつに分ける
左半分を整列する
右半分を整列する
2つの整列済み配列をまとめる要点
O(n log n)
O(n log n)
O(n log n)
はい
補足
各段で全体を一度見て、半分に分ける段がそれほど多くないからです。
配列版では作業用のメモが必要です。
分ける流れと、最後にまとめる流れを分けて見せると整理しやすいです。
動きで確認
ここでは「半分に分かれる様子」を見ながら、上で読んだ内容を動きと結びつけます。
次に見る
比較すると違いがわかりやすいページを先に置いています。