日常的に行う方法とはちょっと違う

何か物を整理するときに、まず大分類で分けて、同じ大分類の物について中分類で分類し、
さらに小分類へというように整頓することはよくある。
これに対して基数ソートはまず最小の単位について整列させて、
次々と上の単位に関する整列を行うことで整列を完了させる。
まるっきり逆方向の方法になっているが、どちらでも最終的にはうまく整列する。

大分類から下位分類へと整列する方法はクイックソートと関係している。
大雑把な性質に注目して整列し、さらに同じ性質をもった各分類ごとに整列する、
という方法は、ある値よりも大きいか小さいかで二分し、
分けた二つのグループについてそれぞれまた二つに分けるというクイックソートの原理と同じである。
これは大きな問題を小問題に分割していくことで問題の強度を減らす分割統治法の考え方である。

分割統治法は人間が日常的に行う考え方だが、基数ソートはそれとはちょっとだけ毛色が違う。
まず最も細かな性質の違いに注目して整列し、より大雑把な性質の違いに関する整列へと進む。
処理は同性質のグループ単位で行わず、常に全体に対して行う。
同じ分類レベルの性質の間では上位分類に関係なく順位を定義できないといけない制約がある。