[Adaptado ENADE 2005 - Ciência da Computação] No processo de ordenação de um vetor cujos os valores não estão ordenados, os números máximos de comparações necessárias para se ordenar um vetor, utilizando o método de ordenação Merge Sort, para vetores com tamanhos 100, 500, 1000, 5000 são, respectivamente, aproximadamente:

A) 900, 1550, 36000 e 330000. B) 600, 5000, 12000 e 12000 C) 500, 9000, 32000 e 210000. D) 1000, 30000, 55000 e 120000 E) 700, 4500, 10000 e 65000

O algoritmo Merge Sort tem uma complexidade de tempo de $O(n \log n)$, onde $n$ é o número de elementos no vetor. Para calcular o número máximo de comparações, podemos usar a fórmula aproximada $n \log_2 n$.

Para $n = 100$: $100 \log_2 100 \approx 700$ Para $n = 500$: $500 \log_2 500 \approx 4500$ Para $n = 1000$: $1000 \log_2 1000 \approx 10000$ Para $n = 5000$: $5000 \log_2 5000 \approx 65000$

Portanto, a opção correta é a E.