Merge sort

Il merge sort divide a metà l'array e riordina ricorsivamente le due parti per poi riunirle.

mergesort(Array A, int p, int r)
  if p < r
    med = (p + r)/2
    mergesort(A, p, med)
    mergesort(A, med+1, r)
    merge(A, p, med, r)

merge(Array A, int p, int med, int r)
  L = []
  left_len = med - p + 1
  for i = 1 to left_len
    push(L, A[p + i-1])

  R = []
  right_len = r - med
  for i = 1 to right_len
    push(R, A[med + i])

  i = 1, j = 1
  for k = p to r
    if i <= left_len and (j > right_len or L[i] <= R[j])
      A[k] = L[i]
      i++
    else
      A[k] = R[j]
      j++

L'algoritmo è corretto per l'invariante dell'ultimo for:

In A[p..k-1] sono ordinati elementi che, come L[i] e R[j], sono minori del resto di L e R

e quando il for termina k = r + 1 quindi l'invariante vale per A[p..r+1-1] cioè l'intero array.

La complessità di merge si può ricavare, sapendo che $n=r-p+1$, da: $$\begin{array}{rl}T(n)& =\Theta (\text{left\_len})+\Theta (\text{right\_len})+\Theta (r-p+1)=\\ & =\Theta (\text{left\_len}+\text{right\_len})+\Theta (n)=\\ & =\Theta (\text{med}-p+1+r-\text{med})+\Theta (n)=\\ & =\Theta (r-p+1)+\Theta (n)=\Theta (n)\end{array}$$ mentre quella di mergesort è $T(n)=2T(\frac{n}{2})+\Theta (n)=\Theta (n\log n)$ per il teorema master.

L'algoritmo è stabile ma non in loco, ed è migliorabile con l'insertion sort su array piccoli.