编辑代码

#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <iostream>
using namespace std;
#define N 10
#define M 100

void print(int *a)
{
    for(int i=0; i<N; ++i)
    {
        printf("%3d", a[i]);
    }
    printf("\n");
}

void merge(int *a, int left, int mid, int right)
{
    //将数组a拷贝到数组b
    int *b = (int*)malloc(sizeof(int) * N);
    memcpy(b, a, sizeof(int)*N);

    //i表示左半边的下标，j表示右半边的下标，k表示结果下标
    int i,j,k;
    for(i=left,j=mid+1,k=left; i<=mid && j<=right; ++k)
    {
        if(b[i] < b[j])
        {
            //如果左半边小，将小的放入a
            a[k] = b[i];
            ++i;
        }
        else
        {
            a[k] = b[j];
            ++j;
        }
    }

    //左半边还有数据
    while(i <= mid)
    {
        a[k] = b[i];
        ++k;
        ++i;
    }

    while(j <= right)
    {
        a[k] = b[j];
        ++k;
        ++j;
    }

    free(b);
    b=NULL;
}

void mergeSort(int *a, int left, int right)
{
    if(left < right)
    {
        //mid的位置并未确定，需要向下递归
        int mid = (left+right) / 2;
        mergeSort(a, left, mid);
        mergeSort(a, mid+1, right);
        merge(a, left, mid, right);
    }
}
int main() {
    srand(time(NULL));
    int *a = (int*)malloc(sizeof(int) * N);
    for(int i=0; i<N; ++i)
    {
        a[i] = rand() % M;
    }

    print(a);

    mergeSort(a, 0, N-1);

    print(a);

    free(a);
    a = NULL;
	return 0;
}