Grokking Timsort

Question

Il y a un (relativement) nouveau type sur le bloc appelé Timsort. Il a été utilisé comme list.sort de Python, et va maintenant être la nouvelle Array.sort Java 7.

Il y a une documentation et petit article de Wikipedia décrivant les propriétés de haut niveau du genre et des évaluations de performance de bas niveau, mais j'étais curieux si quelqu'un peut fournir une pseudocode pour illustrer ce que Timsort fait, exactement, et quels sont les éléments clés qui en font zippy. (Esp. En ce qui concerne le document cité, « Optimiste tri et information complexité Théorique ».)

(Voir aussi liés post StackOverflow.)

Answer 1

Citant la partie pertinente d'un billet de blog maintenant supprimé: : algorithmes de tri Visualisation timsort Python

  

L'activité de fin de timsort est un mergesort qui fonctionne sur les pistes d'éléments pré-triés. Une longueur minimale de course Minrun est choisie pour assurer que les fusions finales sont aussi équilibrée que possible - pour 64 éléments, Minrun se trouve être 32. Avant les fusions commencent, un seul passage est effectué à travers les données pour détecter les pistes pré-existantes de tri éléments. parcours descendant sont gérées par les inversant simplement en place. Si la longueur de course résultante est inférieure à Minrun, il est stimulé à l'aide Minrun sorte d'insertion. Sur un tableau mélangé sans pistes préexistantes importantes, ce processus ressemble exactement à notre estimation ci-dessus: les blocs de pré-tri des éléments Minrun en utilisant le tri par insertion, avant de fusionner avec tri fusion

.

[...]

• timsort trouve une course descendante, et inverse la course en place. Cela se fait directement sur le tableau de pointeurs, donc semble de notre point de vue « instant ».
• La course est maintenant portée à Minrun de longueur à l'aide tri par insertion.
• Pas de course est détecté au début du bloc suivant, et le tri d'insertion est utilisé pour trier le bloc entier. Notez que les éléments triés au bas de ce bloc ne sont pas traités spécialement -. Timsort ne détecte pas court qui commencent au milieu des blocs étant portée à Minrun
• Enfin, mergesort est utilisé pour fusionner les pistes.

Answer 2

Ce changement est passé par les core-libs mailing liste quand il est allé dans la discussion il y a quelques liens utiles et là-bas. Voici les rev web avec des changements de l'examen du code ainsi que le < a href = "http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/timsort.patch" rel = "nofollow noreferrer"> patch d'origine.

Les commentaires dans le code disent:

  

Note de mise en œuvre: Cette mise en œuvre est une société stable, d'adaptation,
   mergesort itératif qui nécessite beaucoup moins que les comparaisons n lg (n)
   lorsque le tableau d'entrée est partiellement triée, tout en offrant la
   la performance d'un mergesort traditionnel lorsque le tableau d'entrée est
   au hasard ordonné. Si le tableau d'entrée est presque triée,
   la mise en œuvre nécessite environ des comparaisons n.
   les besoins de stockage temporaires varient d'une petite constante de
près Sorted    tableaux d'entrée à n / 2 références d'objet pour
d'entrée au hasard commandé    tableaux.

     

La mise en œuvre profite même de monter et
   ordre décroissant dans son tableau d'entrée, et peut profiter de
   ordre croissant et décroissant dans différentes parties du même
   tableau d'entrée. Il est bien adapté à la fusion de deux ou plus des tableaux triés:
   concaténer simplement les tableaux et trier le tableau résultant.
   La mise en œuvre a été adaptée du type de liste de Tim Peters pour Python
    TimSort . Il utilise techiques de « Optimiste
Peter McIlroy    Tri et information complexité Théorique », Actes du
   Quatrième annuelle ACM-SIAM Symposium sur les algorithmes discrets, pp 467-474,
   Janvier 1993.

Enterrée il y a le lien très utile pour les détails d'implémentation Python , et je pense que c'est un excellent endroit pour commencer, suivi du code. Pour être au niveau incroyablement élevé à ce sujet, timsort améliore les performances en remarquant séries de données et triées en tirant parti de cette structure pendant le tri.