Müqayisəli çeşidləmələr Ω(n log n)-dən sürətli ola bilməz (bax: çeşidləmənin xassələri). Amma sərhəd elementlərin müqayisəsinə aiddir. Açarlar haqqında daha çox şey bilsək (kiçik tam ədədlərdir, rəqəmləri var, bərabər paylanıb), açarı indeks kimi işlədib xətti vaxtda çeşidləyə bilərik. Qiyməti verilənlərə qoyulan məhdudiyyətlərdir.
Sayma çeşidləməsi
0..k tam ədədləri üçün: hər qiymətin neçə dəfə rast gəldiyini sayırıq, sayğacları prefiks cəmlərinə çeviririk (count[v] ≤ v elementlərin sayı olur) və elementləri nəticə massivinə yerləşdiririk. Girişi sondan oxusaq, eyni qiymətlərin sonuncusu sonuncu yerə düşür, ona görə çeşidləmə dayanıqlıdır.
a = [4, 2, 2, 8, 3, 3, 1]
k = 8
count = [0] * (k + 1)
for x in a:
count[x] += 1
print("count :", count)
for v in range(1, k + 1):
count[v] += count[v - 1]
print("prefix:", count)count : [0, 1, 2, 2, 1, 0, 0, 0, 1]
prefix: [0, 1, 3, 5, 6, 6, 6, 6, 7]