算法导论读书笔记之归并排序

    归并排序的时间复杂度为O(n*lgn)，但是非in-place算法，使用了额外的空间开销，并且额外的空间

是随着输入规模的增大而增大的。

    归并排序采用分治策略(divisor-and-conquor)

mergeSort.c

#include "mergeSort.h"
#include

int buff[4092];

void mergeSort(int *A, int l, int r)
{
    if(l == r)
        return;

    int m = (l + r) / 2;
   
    printf("mergeSort(A, %d, %d)\n", l, r);

    mergeSort(A, l, m);
    mergeSort(A, m + 1, r);
    merge(A, l, m, r);
}

void merge(int *A, int l, int m, int r)
{
    int i = l;
    int j = m + 1;
    int k = 0;
    while((i <= m) && (j <= r))
    {
        if(A[i] < A[j])
        {
            buff[k++] = A[i++];
        }
        else
        {
            buff[k++] = A[j++];
        }   
    }
    while(i <= m)
    {
        buff[k++] = A[i++];   
    }
    while(j <= r)
    {
        buff[k++] = A[j++];
    }
    for(k = 0, i = l;i <= r;i++)
    {
        A[i] = buff[k++];   
    }
}

mergeSort.h

#ifndef MERGESORT_H
#define MERGESORT_H

void mergeSort(int *A, int l, int r);
void merge(int *A, int l, int m, int r);

#endif

main.c

#include "mergeSort.h"
#include
#include
#include
#include

void print_array(int *a, int len)
{
    int i = 0;
    for(i = 0;i < len;i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}
int main()
{
    int i, len;
    int *A;

    printf("len = ");
    scanf("%d", &len);
   
    if( (A = (int *)malloc(sizeof(int) * len)) == NULL)
    {
        perror(strerror(errno));
        return 1;
    }
    for(i = 0;i < len;i++)
    {
        A[i] = rand() % 100;
    }
   
    printf("Before merge sorting : ");
    print_array(A, len);
   
    mergeSort(A, 0, len - 1);
   
    printf("After merge sorting : ");
    print_array(A, len);
   
    return 0;
}