Für Eingaben der Größe n, für die Werte von n Insertion-Sort Beat Merge-Sort?

Question

In dem Buch Einführung in Algorithmen (Corman) stellt Übung 1.2-2 die folgende Frage zum Vergleich der Implementierungen von Einfügesortierung und Zusammenführungssortierung. Bei Eingaben der Größe n wird die Einfügesortierung in 8n^2 Schritten ausgeführt, während die Zusammenführungssortierung in 64n lg n Schritten ausgeführt wird. für welche Werte von n tut Insertion sort beat merge sort?

Obwohl ich an der Antwort interessiert bin, interessiere ich mich mehr dafür, wie ich die Antwort Schritt für Schritt finde (so dass ich den Prozess wiederholen kann, um irgendwelche zwei gegebenen Algorithmen wenn überhaupt möglich zu vergleichen).

Auf den ersten Blick scheint dieses Problem ähnlich wie die Suche nach dem Break Even-Punkt in Business-Kalkül, eine Klasse, die ich vor mehr als 5 Jahren nahm, aber ich bin mir nicht sicher, so würde jede Hilfe geschätzt werden.

Danke

P/S Wenn meine Tags falsch sind, ist diese Frage falsch kategorisiert oder eine andere Konvention missbraucht wird hier bitte die Züchtigung auf ein Minimum zu begrenzen, wie Ich schreibe zum ersten Mal eine Frage.

Answer 1

Da Sie zu finden sind, wenn Schläge Insertionsort Mergesort

8n^2<=64nlogn 
n^2<=8nlogn 
n<=8logn 

Auf n-8logn = 0 lösen Sie bekommen

n = 43.411 

Also für n<=43 Insertionsort funktioniert besser als Mergesort.