Counting Sort

ちょいちょい勉強したことでも書き留めておこうと思います。
Counting Sortというのを知りました。
sortなんてquick sortとmerge sortだけ知ってりゃ十分やとか思ってたんやけど、CFでこれを使う問題が解けんくて悔しかったから書いときます。
この方法は数列とかのソートより、アルファベットみたいに種類に限りがあるものに対するソートに向いてるみたいです。
abracadabraをソートする時はa,b,c,d,rの数を数えて、それぞれ5,2,1,1,2なのでaaaaabbcdrrとするという感じです。
要するに数えたら後は並べるだけ。ってことです。
数える部分もsortする部分も(連続区間なので)segtreeを使って高速化できる場合があります。