归并排序

代码演示

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>


#define swap(a, b) {\
    __typeof(a) __temp = a;\
    a = b, b = __temp;\
}

#define TEST(arr, n, func, args...) {\
    int *num = (int *)malloc(sizeof(int) * n);\
    memcpy(num, arr, sizeof(int) * n);\
    output(num, n);\
    printf("%s = ", #func);\
    func(args);\
    output(num, n);\
    free(num);\
    printf("\n");\
}


void merge_sort(int *num, int l, int r) {
    if (r - l <= 1) {
        if (r - l == 1 && num[r] < num[l]) {
            swap(num[l], num[r]);
        }
        return ;
    }
    int mid = (l + r) >> 1;
    merge_sort(num, l, mid);
    merge_sort(num, mid + 1, r);
    int *temp = (int *)malloc(sizeof(int) * (r - l + 1));
    int p1 = l, p2 = mid + 1, k = 0;
    while (p1 <= mid || p2 <= r) {
        if (p2 > r || (p1 <= mid && num[p1] <= num[p2])) {
            temp[k++] = num[p1++];
        } else {
            temp[k++] = num[p2++];
        }
    }
    memcpy(num + l, temp, sizeof(int) * (r - l + 1));
    free(temp);
    return ;
}

void output(int *num, int n) {
    printf("[");
    for (int i = 0; i <  n; i++) {
        i && printf(", ");
        printf("%d", num[i]);
    }
    printf("]\n");
}

int main() {
    srand(time(0));
    #define N 20
    int arr[N];
    for (int i = 0; i < N; i++) {
        arr[i] = rand() % N * 40;
    }
    TEST(arr, N, merge_sort, num, 0, N - 1);
    return 0;
}