mergesortdewikipedia :p

/*# split in half
m = n / 2

# recursive sorts
sort a[1..m]
sort a[m+1..n]

# merge sorted sub-arrays using temp array
b = copy of a[1..m]
  i = 1, j = m+1, k = 1
  while i <= m and j <= n,
  a[k++] = (a[j] < b[i]) ? a[j++] : b[i++]
    → invariant: a[1..k] in final position
    while i <= m,
    a[k++] = b[i++]
  → invariant: a[1..k] in final position
*/
/*main (int argc,char **)
{
  int lo= 10, m=7, hi=19;
  int i, j, k;
   // copy both halves of a to auxiliary array b
  for (i=lo; i<=hi; i++)
    b[i]=a[i];

  i=lo; j=m+1; k=lo;
  // copy back next-greatest element at each time
  while (i<=m && j<=hi)
    if (b[i]<=b[j])
      a[k++]=b[i++];
    else
      a[k++]=b[j++];

  // copy back remaining elements of first half (if any)
  while (i<=m)
    a[k++]=b[i++];
}
main (int argc,char **)
{
  int a[],b[];
  merge(10,5,19);

  }*/
  void mezclar(int arreglo1[], int n1, int arreglo2[], int n2, int arreglo3[])
  {
    int x1=0, x2=0, x3=0;

    while (x1<n1 && x2<n2) {
      if (arreglo1[x1]<arreglo2[x2]) {
    arreglo3[x3] = arreglo1[x1];
    x1++;
      } else {
    arreglo3[x3] = arreglo2[x2];
    x2++;
      }
      x3++;
    }
    while (x1<n1) {
      arreglo3[x3] = arreglo1[x1];
      x1++;
      x3++;
    }
    while (x2<n2) {
      arreglo3[x3] = arreglo2[x2];
      x2++;
      x3++;
    }
  }

void mezcla(int vector[], int n)
{
  int *vector1, *vector2, n1, n2,x,y;
  if (n>1)
    {
      if (n%2 == 0)
    n1=n2=(int) n / 2;
      else
        {
      n1=(int) n / 2;n2=n1+1;
        }
      vector1=(int *) malloc(sizeof(int)*n1);
      vector2=(int *) malloc(sizeof(int)*n2);
      for(x=0;x<n1;x++)
    vector1[x]=vector[x];
      for(y=0;y<n2;x++,y++)
    vector2[y]=vector[x];
      mezcla(vector1, n1);
      mezcla(vector2,n2);
      mezclar(vector1, n1, vector2, n2, vector);
      free(vector1);
      free(vector2);
    }
}

int main(){
  int i, vector[] = {2,3,5,7,2,6,1,5,8,3,2};

  mezcla(vector,12);

  for(i=0;i<12;i++)
    printf("%i,\n", vector[i]);

  return 0;
}