Ho un'implementazione dell'ordinamento di fusione in C ++ utilizzando una lista personalizzata doppiamente collegata. Mi viene in mente una grande complessità O di n ^ 2, basata su merge_sort() > slice operazione. Tuttavia, da cosa ho letto , questo algoritmo dovrebbe essere n*log(n) , dove il registro ha una base di due.
Qualcuno può aiutarmi a determinare se sto solo determinando la complessità in modo errato o se l'implementazione può / deve essere migliorata per raggiungere la n*log(n) complessità?
Se desideri un po 'di conoscenze sui miei obiettivi per questo progetto, vedi il mio blog . Ho aggiunto commenti nel codice che descrivono ciò che capisco della complessità di ciascun metodo.
Chiarimento - Mi sto concentrando sull'implementazione del C ++ con questa domanda. Ho un'altra implementazione scritta in Python, ma è stata aggiunta in aggiunta ai miei obiettivi originali.