なぜmergesortはリンクリストの方が優れていますか？

Question

クイックソートではなくリストをソートする際に、マージオールが「行く方法」と考えられるのはなぜですか？ 私はオンラインで見た講義でこれを聞き、いくつかのウェブサイトで見ました。

Answer 1

クイックソートの主な効率源の1つはlocality of referenceです。コンピュータハードウェアが最適化されているため、相互に近いメモリ位置のアクセスがメモリ全体に分散しているメモリ位置へのアクセスより高速になる傾向があります。クイックソートの分割ステップは、前面と背面の近くにある連続する配列要素にアクセスするため、通常は優れたローカリティを備えています。結果として、ヒープソートの場合にはアクセスがより分散されるため、クイックソートは、ヒープソートのような他のソートアルゴリズムよりもはるかに優れている傾向があります。

さらに、クイックソートは、一時的な値を保持する補助配列を作成することなく、インプレースで動作するため、通常、他のソートアルゴリズムよりもはるかに高速です。マージソートのようなものと比べると、補助配列の割り振りと割り当て解除に必要な時間が目に見えることがあるため、これは大きな利点になります。その場で操作することでクイックソートの地域性も向上します。

リンクリストを操作する場合、これらの利点は必ずしも適用されません。リンクされたリストのセルは、しばしばメモリ全体に分散されるため、隣接するリンクされたリストのセルにアクセスするための局所性のボーナスはありません。その結果、クイックソートの大きなパフォーマンス上の利点の1つが食べられます。同様に、マージソートのリンクリストアルゴリズムに余分な補助記憶スペースが必要ないため、インプレースの利点はもはや適用されません。

しかし、quicksortはリンクリストではまだ非常に高速です。マージソートは、リストを半分に均等に分割し、分割ステップを実行するよりもマージを行うための反復ごとの作業が少なくて済むため、高速化する傾向があります。

希望すると便利です。

Answer 2

find（）のコストは、mergesortよりもquicksortにとってより有害です。

マージソートは、データに対してより多くの「短距離」操作を実行するため、リンクリストに適していますが、クイックソートはランダムアクセスデータ構造でより効果的です。