Per gli input di dimensione n, per i quali valori di n fa l'inserimento-sort beat merge-sort?

Question

Nel libro Introduction to Algorithms (Corman), l'esercitazione 1.2-2 pone una domanda sul confronto tra le implementazioni di tipo insertion sort e merge sort. Per gli input di dimensione n, l'ordinamento di inserimento viene eseguito in 8n^2 passaggi mentre si esegue l'unione delle esecuzioni in passaggi 64n lg n; per quale valore di n l'ordinamento per inserimento batte l'unisci merge?

Anche se sono interessato alla risposta, sono più interessato a come trovare la risposta passo dopo passo (in modo da poter ripetere il processo per confrontare eventuali due algoritmi forniti, se possibile).

A prima vista, questo problema sembra simile a qualcosa come trovare il punto di pareggio nel business-calcolo, una classe che ho preso più di 5 anni fa, ma non sono sicuro che ogni aiuto sarebbe apprezzato.

Grazie

P/S Se i miei tag sono corretti, questa domanda è classificato in modo non corretto, o qualche altra convenzione è abusato qui si prega di limitare la chastising al minimo, come questa è la prima volta che metto una domanda.

Answer 1

Dal momento che si è di trovare quando battute insertion sort merge sort

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

sulla soluzione n-8logn = 0 si ottiene

n = 43.411 

Così per n<=43 insertion sort funziona meglio di merge sort.