Problema Extra
--------------

    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.