Vai al contenuto principale

Informatica · Ordinamento

Merge con esaurimento anticipato: contare i confronti

Fondi i due array ordinati $A = [1, 4, 9, 10, 12]$ e $B = [2, 3, 5, 6]$ con la procedura standard di merge: a ogni passo si confrontano i primi elementi non ancora copiati dei due array e si copia il minore (in caso di parità quello di A); quando un array si esaurisce, i restanti elementi dell'altro vengono copiati senza ulteriori confronti. Quanti confronti vengono eseguiti?