Seleção combinada

Merge sort

O merge sort, ou ordenação por mistura, é um exemplo de algoritmo de ordenação do tipo dividir-para-conquistar.

Sua ideia básica consiste em Dividir(o problema em vários sub-problemas e resolver esses sub-problemas através da recursividade) e Conquistar(após todos os sub-problemas terem sido resolvidos ocorre a conquista que é a união das resoluções dos sub-problemas).Como o algoritmo do Merge Sort usa a recursividade em alguns problemas esta técnica não é muito eficiente devido ao alto consumo de memória e tempo de execução.

Os três passos úteis dos algoritmos dividir-para-conquistar, ou divide and conquer, que se aplicam ao merge sort são:

1. Dividir: Dividir os dados em subsequências pequenas;

2. Conquistar: Classificar as duas metades recursivamente aplicando o merge sort;

3. Combinar: Juntar as duas metades em um único conjunto já classificado.

Características

• Complexidade de tempo: Θ(n log2 n)

• Complexidade de espaço: Θ(n)

Observações

• É possível implementar o merge sort utilizando somente um vetor auxiliar ao longo de toda a execução, tornando assim a complexidade de espaço adicional igual a Θ(n log n).

• É possível também implementar o algoritmo com espaço adicional Θ(1)

• Algoritmo Criado por Von Neumann em 1945.

Desvantagens

Utiliza funções recursivas

• Gasto extra de memória, o algorítimo cria uma cópia do vetor para cada nível da chamada recursiva, totalizando um uso adicional de memória igual á (n log n)

Código em C

void merge(int vec[], int vecSize) {

int mid;

int i, j, k;

int* tmp;

tmp = (int*) malloc(vecSize * sizeof(int));

if (tmp == NULL) {

exit(1);

}

mid = vecSize / 2;

i = 0;

j = mid;

k = 0;

while (i < mid && j < vecSize) {

if (vec[i] <= vec[j]) {

tmp[k] = vec[i++];

}

else {

tmp[k] = vec[j++];

}

++k;

}

if (i == mid) {

while (j < vecSize) {

tmp[k++] = vec[j++];

}

}

else {

while (i < mid) {