マージソート
更新日:
用語解説
マージソートは、データを半分に分けることを繰り返し、整列した部分どうしを併合（マージ）しながら全体を整列する方法です。
■ 試験で押さえるポイント
分割統治法の代表的なアルゴリズムです。
計算量は、最悪でもO(n log n)です。
併合のために、データと同じ大きさの作業領域が必要です。
■ 過去問での着眼点
最悪でもO(n log n)で、安定な整列である点を押さえます。
例: [5,3,8,1]を[5,3]と[8,1]に分け、[3,5]と[1,8]を併合して[1,3,5,8]にします。