Melhorando o mergesort

Apresentamos em um post antigo denominado Recursividade - Parte 2 ou MergeSort como implementar um algoritmo bastante eficiente de ordenação. Este algoritmo é o mergesort que usa o método de dividir para conquistar. Como o mergesort dividi a lista de elementos que devem ser ordenados em sublistas, podemos melhorar um pouco o desempenho em ambientes de multiprocessamento. Como? Fazendo que as sublistas sejam processadas em paralelo pelos diversos processadores que possuímos.

Vamos ver no vídeo como podemos implementar threads com mergesort para torná-lo mais rápido via paralelismo. Note que não estamos alterando o número de operações, portanto a complexidade do algoritmo é a mesma.