Merge Sort

merge_sort.c

/*
MERGE(A, p, q, r)
1 n1 ← q - p + 1
2 n2 ← r - q
3 create arrays L[1...n1 + 1] and R[1...n2 + 1]
4 for i ← 1 to n1
5     do L[i] ← A[p + i - 1]
6 for j ← 1 to n2
7     do R[j] ← A[q + j]
8 L[n1 + 1] ← ∞
9 R[n2 + 1] ← ∞
10 i ← 1
11 j ← 1
12 for k ← p to r
13     do if L[i] ≤ R[j]
14     then A[k] ← L[i]
15         i ← i + 1
16     else A[k] ← R[j]
17         j ← j + 1
*/
#include <stdio.h>

typedef unsigned int  uint;

void MERGE(uint A[], int p, int q, int r)
{
    int n1 = q - p + 1;
    int n2 = r - q;
    int i = 0;
    int j = 0;
    int k = 0;
    
    uint *L = NULL;
    uint *R = NULL;

    L = (uint *)malloc((n1+2)*sizeof(uint));
    R = (uint *)malloc((n2+2)*sizeof(uint));

    for(i=1; i<=n1; i++)
    {
        L[i] = A[p+i-1];
    }

    for(j=1; j<=n2; j++)
    {
        R[j] = A[q+j];
    }
    
    //sentiel card
    L[n1+1] = ~0;
    R[n2+1] = ~0;
    i = 1;
    j = 1;

    for(k=p; k<=r; k++)
    {
        if(L[i] <= R[j])
	    {
	        A[k] = L[i];
	        i += 1;
	    }
	    else 
	    {
	        A[k] = R[j];
	        j += 1;
	     }
    }
 
    free(L);
    free(R);
}

void MERGE_SORT(uint A[], int p, int r)
{
   if(p >= r)
       return;
   int q = 0;
   q = (p+r) >> 1;
   
  
   MERGE_SORT(A, p, q);
   MERGE_SORT(A, q+1, r);
   MERGE(A, p, q, r);
}

int main()
{
   uint A[] = {0, 2, 4, 5, 7, 1, 2, 3, 6};
   int length = 0;
   int i = 0;

   length = sizeof(A) / sizeof(uint);
   MERGE_SORT(A, 1, length);

   for(i=1; i<length; i++)
   {
       printf("%d, ", A[i]);
   }
   getchar();
}