Python-un sorted() və list.sort() funksiyaları Timsort (Tim Peters, 2002) işlədir: verilənlərdə artıq mövcud olan sıradan istifadə edən birləşdirmə və daxiletmə ilə çeşidləmənin hibridi. O, dayanıqlıdır, pis halda O(n log n), çeşidlənmiş girişdə isə O(n) vaxt aparır. API özü Python-da siyahıların çeşidlənməsi dərsində təsvir olunub.
Timsort necə işləyir
- Run-lar. Massivdə təbii hissələr axtarılır: azalmayan və ya ciddi azalan hissələr; azalan hissə yerində çevrilir.
- minrun. Qısa run-lar kiçik hissələrdə sürətli olan ikili daxiletmə ilə
minrun-a (təxminən 32–64 element) qədər uzadılır. - Birləşdirmə yığını. Run-lar yığına qoyulur və ölçülərin balansını saxlayan qaydalarla birləşdirilir, buna görə birləşdirmə ağacının dərinliyi
O(log n)-dir. - Gallop. Birləşdirmə zamanı bir run ardıcıl çox müqayisə udursa, Timsort eksponensial axtarışa (gallop) keçir və bütöv hissəni birdəfəlik köçürür.
Nəticədə çeşidləmə dayanıqlıdır, demək olar ki, çeşidlənmiş verilənlərdə n-ə, digər hallarda n log n-ə yaxındır. Yuxarıdakı şəkil sadələşdirilmiş modeldir.
