n種類だとおよそ平均n*log n くらいだね。(nが十分大きいとき)