Nel frammento di codice sottostante viene presentato l’algoritmo di ordinamento Merge Sort. L’algoritmo Merge Sort è un algoritmo che sfrutta le tecniche di Ricorsione e di Divide et Impera per ordinare un vettore di elementi.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>

void stampa(int *a, int n);
void mergeSort(int *a, int n);

int main(void) {
  int a[10] = {5, 1, 3, 99, 45, 63, 21, 34, 0, 84}; // elementi da ordinare
  int n = 10;  // numero di elementi

  stampa(a, n);
  mergeSort(a, n);
  stampa(a, n);

  return 1;
}

// stampo tutti i valori presenti nel vettore
void stampa(int *a, int n) {
  int i;

  for(i=0; i<n; i++)
    printf("%d ", a[i]);

  printf("\n");
}

// passo alla funzione il puntatore al vettore da ordinare e la sua dimensione
void mergeSort(int *a, int n) {
  int *a1 = NULL, *a2 = NULL;
  int a1_n, a2_n;
  int i, x, y;

  // se il vettore è formato un solo elemento allora è già ordinato, altrimenti procedo
  if(n == 1)
   return;

  // calcolo le nuove dimensione dei sotto-vettori di a
  a1_n = n/2;
  a2_n = n/2;
  if(n%2!=0) { // se n è dispari
    a1_n++; //ceil
  }

  // creo i nuovi sotto-vettori
  a1 = realloc(a1, a1_n*sizeof(int));
  a2 = realloc(a2, a2_n*sizeof(int));
  if(a1 == NULL || a2 == NULL) {
    exit(1);
  }

  memcpy(a1, a, a1_n*sizeof(int));         // copio la prima metà dell'array
  memcpy(a2, &a[a1_n], a2_n*sizeof(int));  // copio la seconda metà dell'array

  mergeSort(a1, a1_n);  // reitero la funzione sulla prima metà
  mergeSort(a2, a2_n);  // reitero la funzione sulla seconda metà

  // ordino i risultati
  x=0;  // dimensione del primo array
  y=0;  // dimensione del secondo array

  for(i=0; i<(a1_n+a2_n); i++) {
   if((x<a1_n && a1[x]<=a2[y]) || y>=a2_n) { // se (a1 non è vuoto e a1<=a2) oppure se a2 è vuoto
    a[i] = a1[x];
    x++;
   }
   else {
    a[i] = a2[y];
    y++;
   }
  }  

  free(a1);
  free(a2);
}

Per maggiori informazioni circa la sintassi del linguaggio si faccia riferimento alla guida al Linguaggio C.