HERGHELEGIU

Another sort method is merge sort

MERGE-SORT(A,p,r)

T(n) is THETA(n lg n)
Insertion sort run faster for low n because of the constant factors.
We can use insertion sort when subproblems is sufficient small.

MERGE-SORT(A,p,r)
{
    if ( p < r )
    {
        q = (p+r)/2;
        MERGE-SORT(A,p,q);
        MERGE-SORT(A,q+1,r);
        MERGE(A,p,q,r);
    }
}

 

MERGE(A,p,q,r)
{
    int i = p;
    int j = q+1;
    int k = p;
    while( i <=q || j<=r )
    {
        min = 0;
        if ( i<=q && ( !(j<=r) || (j<=r && A[i] < A[j]) ) )
        {
            min = A[i];
            i++;
        }
        else
        {
            min = A[j];
            j++;
        }
 
        B[k] = min;
        k++;
    }
    
    for( i=p; i<=r; i++ )
        A[i] = B[i];
}

 

if ( i<=q && ( !(j<=r) || (j<=r && A[i] < A[j]) ) )

can be rewrite as

if ( i<=q && ( !(j<=r) || (A[i] < A[j]) ) )


Read more on Wikipedia Merge Sort