DC-UFRPE/Bacharelado em Ciência da Computação/Algoritmos e Estruturas de Dados/Mergesort

Mergesort

Mergesort é um algoritmo recursivo que tem o proposito de resolver o problema de ordenar vetores A[1..n] ou A[p..r] usando o conceito de divisão e conquista.

Seja p ≤ r um vetor que começa em p e termina e r e p = r o caso mais básico da recursão.

O algoritmo recebe um vetor A e é escrito da seguinte forma:

Mergesort (A, p, r)

1  se p < r

2  q := ⌊(p+r)/2⌋

3  Mergesort (A, p, q)

4  Mergesort (A, q+1, r)

5  Intercala (A, p, q, r)

A recursão é feita dividindo o vetor em duas partes até o caso base e depois sobe novamente na recursão usando a função "Intercala".

Intercala (A, p, q, r)

6  para i := p até q

7  B[i] := A[i]

8  para j := q+1 até r

Exemplificação das etapas do algoritmo.

9  B[r+q+1−j] := A[ j]

10  i := p

11  j := r

12  para k := p até r

13  se B[i] ≤ B[ j]

14  A[k] := B[i]

15  i := i+1

16  senão A[k] := B[ j]

17  j := j−1

A função intercala recebe vetores crescentes A[p .. q] e A[q+1 .. r] e rearranja o vetor A[p .. q.. r] de modo que ele fique crescente. O desempenho do mergesort é Θ(n lg n).