归并排序算法代码c++

归并排序是一种经典的排序算法，它基于分治法的思想。下面是归并排序的C代码实现：

#include <stdio.h>

// 合并两个有序数组
void merge(int arr[], int left[], int right[], int leftLen, int rightLen) {
    int i = 0, j = 0, k = 0;

    // 比较两个数组的元素，并将较小的元素放入原数组中
    while (i < leftLen && j < rightLen) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }

    // 将剩余的元素放入原数组中
    while (i < leftLen) {
        arr[k++] = left[i++];
    }

    while (j < rightLen) {
        arr[k++] = right[j++];
    }
}

// 归并排序
void mergeSort(int arr[], int len) {
    if (len <= 1) {
        return;
    }

    int mid = len / 2;
    int left[mid];
    int right[len - mid];

    // 将原数组分为两个子数组
    for (int i = 0; i < mid; i++) {
        left[i] = arr[i];
    }

    for (int i = mid; i < len; i++) {
        right[i - mid] = arr[i];
    }

    // 对两个子数组进行递归排序
    mergeSort(left, mid);
    mergeSort(right, len - mid);

    // 合并两个有序子数组
    merge(arr, left, right, mid, len - mid);
}

// 测试
int main() {
    int arr[] = {9, 5, 7, 1, 3};
    int len = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, len);

    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}