L'exécution d'un tri de fusion modifié par rapport au tri par fusion?

Question

De wikipedia, https://en.wikipedia.org/wiki/Merge_algorithm#Application

Dans le diagramme, disons que nous considérons la ligne du milieu des nombres (aiderait si quelqu'un peut poster l'image ici). Quel serait le temps d'exécution de l'algorithme si je l'ai modifié pour:

• Fusionner 38 et 27, puis trier les nombres dans l'ordre croissant. (27, 38)
• Fusionner le résultat de dessus avec 43, puis trier les nombres dans l'ordre croissant. (27, 38, 43)
• Fusionner le résultat de dessus avec 3, puis trier les nombres dans l'ordre croissant. (3, 27, 38, 43).
• ... Et ainsi de suite jusqu'à ce que j'ai une liste entièrement triée.

Ceci est un moyen extrêmement inefficace pour trier (je peux dire intuitivement - dans le pire des cas, le nombre ajouté échangerais avec chaque numéro dans la liste) mais je ne suis pas sûr de savoir comment il se compare (en termes de justifier mon analyse) pour fusionner le temps O (n log n).

Des pensées?

Answer 1

L'algorithme que vous décrivez est le type d'insertion - vous construisez une liste croissante de valeurs dans l'ordre trié en ajoutant un élément à la fois. Cela signifie que le runtime correspond au tri d'insertion - linéaire si le tableau est trié, en moyenne quadratique, etc.