マージの空間オーバーヘッド
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/18 08:12 UTC 版)
「ティムソート」の記事における「マージの空間オーバーヘッド」の解説
元のマージソートの実装はインプレースではなく、N（データサイズ）のスペースオーバーヘッドがあります。インプレースマージソートの実装は存在しますが、時間のオーバーヘッドが高くなります。落としどころとして、ティムソートでは、Nよりも時間オーバーヘッドと空間オーバーヘッドが小さいマージソートを実行します。 最初に、ティムソートは二分探索を実行して、2番目の並びの最初の要素が最初の順序付けられた並びに挿入される場所を見つけます。次に、同じアルゴリズムを実行して、最初の並びの最後の要素が2番目の順序付けられた並びに挿入される場所を見つけ、順序付けを維持します。これらの場所の前後の要素はすでに正しい場所にあり、マージする必要はありません。次に、2つの並びの残りの要素のうち小さい方が一時メモリにコピーされ、要素は大きい方の並びとマージされて、現在は空き領域になります。最初の並びが小さい場合、マージは最初から始まります。 2番目が小さい場合、マージは最後から始まります。この最適化により、必要な要素の移動数、実行時間、および一般的な場合の一時的なスペースのオーバーヘッドが削減されます。 例：2つの並び[1、2、3、6、10]と[4、5、7、9、12、14、17]をマージする必要があります。両方の並びはすでに個別にソートされていることに注意してください。 2番目の並びの最小要素は4であり、その順序を維持するために、最初の並びの4番目の位置に追加する必要があります（並びの最初の位置が1であると想定）。最初の並びの最大要素は10であり、順序を維持するために2番目の並びの5番目の位置に追加する必要があります。したがって、[1、2、3]と[12、14、17]はすでに最終位置にあり、要素の移動が必要な並びは[6、10]と[4、5、7、9]です。この知識があれば、5ではなくサイズ2の一時バッファを割り当てるだけで済みます。
※この「マージの空間オーバーヘッド」の解説は、「ティムソート」の解説の一部です。
「マージの空間オーバーヘッド」を含む「ティムソート」の記事については、「ティムソート」の概要を参照ください。
- マージの空間オーバーヘッドのページへのリンク
