Est-il plus rapide de trier une liste après avoir inséré des éléments ou les avoir ajoutés à une liste triée ?

Question

Si j’ai une liste triée (disons quicksort à trier), si j’ai beaucoup de valeurs à ajouter, est-il préférable de suspendre le tri et de les ajouter à la fin, puis de trier ou d’utiliser un hachage binaire pour placer correctement les éléments tout en les ajoutant. Est-ce que cela fait une différence si les éléments sont aléatoires, ou déjà plus ou moins dans l’ordre?

Answer 1

Habituellement, il est de loin préférable d’utiliser un tas. en bref, il répartit le coût du maintien de l’ordre entre le pousseur et le préparateur. Les deux opérations sont O(log n), au lieu de O(n log n), comme la plupart des autres solutions.