Problema extra da prova de CANA

Disponível no site de CAnA.

     O algoritmo apresentado na prova essencialmente separa os
 n/2 menores elementos do vetor dos n/2 maiores elementos.
 Este algoritmo pode ser utilizado como sub-rotina de um
 algoritmo de ordenacao cuja ideia e´, primeiramente, colocar
 os n/2 menores elementos na primeira metade do vetor, e os
 n/2 maiores elementos na segunda metade. Em seguida, aplicamos
 a rotina X ´as duas metades do vetor, dividind-o em 4 grupos:

        * os n/4 menores,
        * os n/4 maiores da primeira metade,
        * os n/4 menores da segunda metade,
        * os n/4 maiores.

 Repetindo este processo recursivamente, o vetor fica eventualmente
 ordenado.

     A analise do item (d) mostra que o algoritmo X executa em
 tempo Theta(n log n), e no item (f) obtemos que o algoritmo
 de ordenacao resultante executa em tempo Theta (n (log n)^2 ).

     Uma observacao imediata e´ que o tempo de execucao do algoritmo X
 e´ suficiente para ordenar o vetor inteiro, enquanto ele apenas separa
 os menores dos maiores. Ou seja, em principio, este processo parece
 ineficiente.

     Entretanto, a ideia e´ que o algoritmo X pode ser executado em
 paralelo de maneira extremamente eficiente, o que leva a uma
 algoritmo de ordenacao paralelo tambem bastante eficiente.

     Suponha que voce tem ´a sua disposicao n processadores, e que
 se duas comparacoes envolvem elementos distintos, entao elas podem
 ser executadas em paralelo no tempo de apenas uma comparacao.

 a) Descreva uma versao paralela do algoritmo X que faca uso das
   suposicoes acima da maneira mais eficiente possivel.

 b) Analise o tempo de execucao do seu algoritmo.

 c) Analise o tempo de execucao do algoritmo de ordenacao obtido
   com a versao paralela do algoritmo X.