Vai al contenuto principale

Informatica · Ordinamento

Confronti minimi di merge sort su 7 elementi

Considera il merge sort che divide ogni array di lunghezza n nelle due metà di lunghezze $\lfloor \frac{n}{2} \rfloor$ (sinistra) e $\lceil \frac{n}{2} \rceil$ (destra), le ordina ricorsivamente e le fonde con il merge standard (un confronto per ogni elemento copiato finché entrambe le parti hanno elementi residui). Qual è il numero minimo di confronti che questo algoritmo può eseguire su un array di 7 elementi distinti?