归并排序

#include <stdio.h>
#include <limits.h>

void merge(int *A, int start, int mid, int end);
void mergeSort(int *A, int start, int end);
void myPrint(int *A, int len);

int
main(void)
{
        int a[] = {1,3,5,7,9,0,2,4,6,8,0};
        int len = sizeof(a)/sizeof(a[0]);

        myPrint(a, len);
        mergeSort(a, 0, len-1);
        myPrint(a, len);

        return (0);
}

void
myPrint(int *A, int len)
{
        printf("Enter: ");
        int i = 0;
        for (i = 0; i < len; i++) {
                printf("%d,",*(A+i));
        }
        printf("\n");
}

void
merge(int *A, int start, int mid, int end)
{
        int n1, n2;
        n1 = mid - start + 1;
        n2 = end - mid;

        n1++;
        n2++;

        int L[n1], R[n2];

        int i, j, k;
        for (i = 0; i < n1-1; i++) {
                L[i] = *(A+start+i);
        }
        for (j = 0; j < n2-1; j++) {
                R[j] = *(A+mid+j+1);
        }

        L[i] = INT_MAX;
        R[j] = INT_MAX;

        i = 0;
        j = 0;

        for (k = start; k <= end; k++) {
                if (L[i] <= R[j]) {
                        *(A+k) = L[i];
                        i++;
                } else {
                        *(A+k) = R[j];
                        j++;
                }
        }
}

void
mergeSort(int *A, int start, int end)
{
        int mid;
        if (start < end) {
                mid = (start+end)/2;
                mergeSort(A, start, mid);
                mergeSort(A, mid+1, end);
                merge(A, start, mid, end);
        }
}

稳定性：稳定
T(n): O(nlgn)
S(n): O(n)