void mergesorted(SeqList* sq, SeqList sl, SeqList s2) { }怎么实现mergesort算法

在给定的代码片段中，`mergesorted` 函数实现了合并排序的前半部分，即合并两个已经排好序的序列（sl 和 s2），但缺少了递归分治的核心部分，也就是将原输入列表（`sq`）按顺序分割成小块并排序的过程。下面是完整的合并排序的实现，包括分割、递归以及最后的合并：

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

typedef struct SeqList {
    int n;
    int* a;
} SeqList;

void merge(SeqList* result, SeqList* left, SeqList* right) {
    int i = 0, j = 0, k = 0;

    while (i < left->n && j < right->n) {
        if (left->a[i] <= right->a[j]) {
            result->a[k++] = left->a[i++];
        } else {
            result->a[k++] = right->a[j++];
        }
    }

    while (i < left->n) {
        result->a[k++] = left->a[i++];
    }
    while (j < right->n) {
        result->a[k++] = right->a[j++];
    }
}

SeqList* mergesort(SeqList* sq, int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        SeqList* left = malloc(sizeof(SeqList));
        SeqList* right = malloc(sizeof(SeqList));

        left->n = mid - low + 1;
        left->a = malloc(left->n * sizeof(int));
        right->n = high - mid;
        right->a = malloc(right->n * sizeof(int));

        memcpy(left->a, &sq->a[low], left->n * sizeof(int));
        memcpy(right->a, &sq->a[mid + 1], right->n * sizeof(int));

        mergesort(left, low, mid);
        mergesort(right, mid + 1, high);

        merge(sq, left, right);
        free(left->a);
        free(right->a);
    }
    return sq;
}

// 主函数测试
int main() {
    SeqList sl = {5, 2, 9, 1};
    SeqList s2 = {8, 3, 7, 4};
    SeqList* sq = malloc(sizeof(SeqList));
    sq->n = sl.n + s2.n;
    sq->a = malloc(sq->n * sizeof(int));
    memcpy(sq->a, sl.a, sl.n * sizeof(int));
    memcpy(&sq->a[sl.n], s2.a, s2.n * sizeof(int));

    mergesort(sq, 0, sl.n + s2.n - 1);

    for (int i = 0; i < sq->n; i++) {
        printf("%d ", sq->a[i]);
    }
    free(sq->a);
    free(sq);
    return 0;
}