Merge Sort

The merge sort has a worst case running time of Θnlg(n).

// Merge Sort - Divide  and Conquer /Recurssive method.
// merge two sorted arrays A[l,...m] and A[m+1,..., r]
// to form a single sorted array A[l,...,r]
void merge(int *A, int l, int m, int r)
{
    int n1= m -l +1; // The number of elements in the left array.
    int n2 = r -m;   // The number of elements in the right array.
    int L[n1+1], R[n2+1];
    for ( int i = 0; i < n1; ++i) L[i] = A[l + i ];
    for ( int i = 0; i < n2; ++i) R[i] = A[m + i + 1];
    L[n1] = 9999; // sentinel element
    R[n2] = 9999;

    int i = 0 , j = 0;

    for( int k = l; k <= r;  ++k)
    {
        if ( L[i] <= R[j] )
        {
            A[k] = L[i];
            ++i;
        }
        else
        {
            A[k] = R[j];
            ++j;
        }
    }
} // end of merge()