Ordinamento: Merge Sort

Problema: Data una sequanza di $n$ numeri $A= [a_0,\, \dots\,, a_{n-1}]$, ordinarla in modo crescente.
Soluzione: Ricorsiva (Merge Sort)
Complessità: $\Theta(n\log n)$

Come tutti i metodi ricorsivi, anche merge sort divide il problema fino a quando non si trova a risolvere un problema dello stesso tipo ma banale nella risoluzione. In questo caso la funzione merge_sort() divide la sequenza $A$ fino a quando non si ritrova con una sottosequenza di un solo elemento il cui ordine è già stabilito. Nella figura sotto, al terzo livello di ricorsione, i singoli elementi sono ordinati per definizione.

Arrivati all'ultimo livello di ricorsione, dove tutti gli elementi sono ordinati, si può risalire ed unire le varie parti ordinandole. In questo caso è la funzione merge() che si occupa di questo.

#include <stdio.h>
#include <math.h>
 
void print_vector(int *m, int n);
void merge(int *a, int i, int m, int j);
void merge_sort(int *a, int i, int j);
 
int main(int argc, char *argv[], char *envp[])
{
 int a[8] = { 5, 2, 4, 6, 1, 3, 8, 2 };
 int n = sizeof(a) / sizeof(int);
 merge_sort(a, 0, 7);
 print_vector(a, n);
 
 return 0;
}
 
void merge_sort(int *a, int i, int j)
{
 if (i < j)
 {
  // divide in due la sequenza che va dall'indice i all'indice j
  int m = floor((i + j) / 2);
  merge_sort(a, i, m);
  merge_sort(a, m + 1, j);
  // riunisce le due sequenze ordinandole e ottenendone una di j-i+1 elementi
  merge(a, i, m, j);
 }
}
 
void merge(int *a, int i, int m, int j)
{
 // numero di elementi degli array temporanei sinistro e destro
 int n1 = m - i + 1;
 int n2 = j - m;
 
 // array temporanei sinistro e destro
 int* left = new int[n1];
 int* right = new int[n2];
 
 // inizializza array sinistro
 for (int k = 0; k < n1; ++k)
 {
  left[k] = a[i + k];
 }
 
 // inizializza array destro
 for (int k = 0; k < n2; ++k)
 {
  right[k] = a[m + 1 + k];
 }
 
 // merge ordinato in A dei due array temporanei
 int p = 0;
 int q = 0;
 for (int k = i; k <= j && p < n1 && q < n2; ++k)
 {
  if (left[p] <= right[q])
  {
   a[k] = left[p];
   ++p;
  }
  else
  {
   a[k] = right[q];
   ++q;
  }
 }
 
 // svuota left
 for (int k = i + q + p; p < n1; ++k, ++p)
  a[k] = left[p];
 
 // svuota right
 for (int k = i + p + q; q < n2; ++k, ++q)
  a[k] = right[q];
 
 delete[] left;
 delete[] right;
}
 
void print_vector(int *m, int n)
{
 for (int i = 0; i < n; ++i)
 {
  printf("%d ", m[i]);
 }
 printf("\n");
}

Riferimenti:
[1] Introduzione agli algoritmi e strutture dati - Cormen, Leiserson, Rivest, Stein
[2] https://it.wikipedia.org/wiki/Merge_sort