ティムソート、クイックソート、マージソートなどのアルゴリズムは、「現実世界」のソート方法を支配しています。これらの比較ソートのケースは非常に実用的です。さまざまな環境で最もパフォーマンスが高く、安定した、多目的のソートアルゴリズムであることが示されています。
ただし、コンピューターで並べ替えるほとんどすべてが可算/半順序であるように見えます。数字、文字、文字列、さらには関数でさえ、いくつかの意味のある非比較ソート方法に適しています。ここでの候補は基数ソートです。一般に、O（n * log（n））よりも高速に動作し、多くの場合、O（K * n）-Kの複雑さでn * log（n）の理論的な比較ソート制限を大幅に上回ります。特定のアイテムを表すために必要なビット数です。
何が得られますか？
比較の並べ替えは、非常に優れた抽象化に基づいています。必要なのは、2つの要素を比較する方法だけです。次に、言語に応じて、テンプレート（c ++）、インターフェイス（java）、型クラス（haskell）、関数オブジェクト（javascript）などを使用して、任意の型を保持できるコンテナーを並べ替えることができます。必要なのは、比較を実装することだけです。 。
任意のタイプの基数ソートをどのように実装しますか？:)
基数ソートの速度は、キーの長さによって異なります。文字列のような長いキーがある場合、基数ソートは非常に遅くなる可能性があります。
さらに、少数のアイテムのみをソートする場合、初期化コストが実際のソートを大幅に上回る可能性があります。
たとえば、8ビット基数を使用して32ビット整数を並べ替える場合、256バケットのリストの少なくとも4倍を初期化する必要があります-これを並べ替えるアイテムが20程度しかない場合、80スワップは約よりもはるかに遅くなりますクイックソートに必要な最大200の比較/スワップ。
文字列のように、より長いものを並べ替える場合、最も長い文字列の各文字に対してバケットの初期化が必要になります。これはさらに悪い場合があります。
基数ソートは、整数キーを使用してオブジェクトをソートする場合にのみ役立ちます。実際のパフォーマンスの観点からは、キーの長さに大きく依存します。任意のオブジェクトをソートする一般的なケースでは、これでは十分ではありません。したがって、比較ベースのソートが必要です。