Merge sort

Il merge sort, ordinamento a fusione, così come il quick sort, si basa sul paradigma del divide et impera. Il problema (nel nostro caso di ordinamento) viene suddiviso in tanti sottoproblemi di difficoltà man mano inferiore (l'insieme iniziale viene cioè suddiviso). Il merge sort opera dividendo l'array da ordinare in due met à e affina tale partizione fi no ad isolare ogni singolo elemento. La successiva fase, quindi, prevede la costruzione di un array ordinato operando una vera e propria fusione degli insiemi che man mano vengono ordinati. Di seguito propongo una realizzazione dell'algoritmo in C:

/* mergesort */
#include <stdio.h>

#define LENGTH 10

void mergeSort(int *array, int begin, int end);
void merge(int *array,int begin, int middle, int end);

int main(void) {
   int i,array[LENGTH]={1,8,4,0,2,5,6,3,7,9};
   mergeSort(array,0,LENGTH);
   printf("array: ");
   for (i=0;i<LENGTH;i++)
      printf("%d, ",array[i]);
   printf("\b\b;\n");
   return 0;
}

void mergeSort(int *array, int begin, int end) {
   int middle;
   if (begin<end) {
      middle=(end+begin)/2;
      mergeSort(array,begin,middle);
      mergeSort(array,middle+1,end);
      merge(array,begin,middle,end);
   }
}

void merge(int *array,int begin, int middle, int end) {
   int i,j,k,temp[LENGTH];
   i=begin;
   j=middle+1;
   k=0;
   while ((i<=middle) && (j<=end)) {
      if (array[i]<=array[j])
         temp[k++]=array[i++];
      else
         temp[k++]=array[j++];
   }
   while (i<=middle)
      temp[k++]=array[i++];
   while (j<=end)
      temp[k++]=array[j++];
   for (k=begin;k<=end;k++)
      array[k]=temp[k-begin];
}