Daxiletmə ilə çeşidləmə əlinizdəki oyun kartlarını düzmək kimi işləyir: sol hissə artıq çeşidlənib, hər yeni element isə həmin hissədə öz yerinə qoyulur. Alqoritm sadədir, dayanıqlıdır, yerində işləyir və demək olar ki, çeşidlənmiş verilənlərdə çox sürətlidir. Terminlər (dayanıqlıq, adaptivlik) üçün bax: çeşidləmənin xassələri.

5 2 4 6 1 3 üçün daxiletmə ilə çeşidləmə
5 2 4 6 1 3 üçün daxiletmə ilə çeşidləmə

Alqoritm və invariant

x = a[i] götürürük və çeşidlənmiş a[:i] hissəsində x-dən böyük hər elementi bir mövqe sağa sürüşdürürük. Sonra x-i boşalmış yerə qoyuruq. İnvariant: i addımından əvvəl a[:i] ilkin ilk i elementdən ibarətdir və çeşidlənib.

python
a = [5, 2, 4, 6, 1, 3]
for i in range(1, len(a)):
    x = a[i]
    j = i - 1
    while j >= 0 and a[j] > x:
        a[j + 1] = a[j]
        j -= 1
    a[j + 1] = x
    print("insert", x, "->", a)
text
insert 2 -> [2, 5, 4, 6, 1, 3]
insert 4 -> [2, 4, 5, 6, 1, 3]
insert 6 -> [2, 4, 5, 6, 1, 3]
insert 1 -> [1, 2, 4, 5, 6, 3]
insert 3 -> [1, 2, 3, 4, 5, 6]

Realizasiya

j >= 0 and a[j] > x şərti əvvəl sərhədi yoxlayır, sonra müqayisə edir. Ciddi > bərabər elementləri tərpətmir, ona görə çeşidləmə dayanıqlıdır.