C ++合并排序的链表未对前两个索引进行排序

试图弄清楚如何以递归方式合并排序的链表时，我有点迷失了。我尝试遵循一些指南，但是所有指针和递归都让我有些迷茫。一旦列表中的每个节点只有一个节点，就好像问题出在合并功能上。

我有一个Node课程和一个列表课程。我省略了其他成员函数以使其更具可读性。这是课程。抱歉，某些变量名并不是函数中最好的。

class Node {
  public:
    int val;
    Node *next;
};

class Linked_list {
  private:
    unsigned int length;
    Node *head;
    Node *tail;
  public:
    void sort_ascending();
    void merge_sort(Node **);
    void halve(Node *&, Node *&, Node *&);
    Node* merge(Node *, Node *);
};

我从sort_ascending()创建Node指针开始，将其设置为列表中的第一个节点，然后merge_sort使用指针作为参数进行调用。

void Linked_list::sort_ascending() {
    Node *h = head->next;
    merge_sort(&h);
}

merge_sort检查前两个索引是否为NULL，如果是则返回。否则，链接列表将减半。

void Linked_list::merge_sort(Node **h) {
    Node *t = *h;
    Node *a;
    Node *b;
    if ((t == NULL) || (t->next == NULL)) {
        return;
    }
    halve(t, a, b);
    merge_sort(&a);
    merge_sort(&b);
    *h = merge(a, b);
    return;
}

这是将列表分成两半的功能。

void Linked_list::halve(Node *&t, Node *&a, Node *&b) {
    Node *h1 = t;
    Node *h2 = t->next;
    while (h2 != NULL) {
        h2 = h2->next;
        if (h2 != NULL) {
            h1 = h1->next;
            h2 = h2->next;
        }
    }
    a = t;
    b = h1->next;
    h1->next = NULL;
}

最后是合并功能。

Node *Linked_list::merge(Node *a, Node *b) {
    Node *h = NULL;
    if (a == NULL) {
        return b;
    }
    if (b == NULL) {
        return a;
    }
    if (a->val <= b->val) {
        h = a;
        h->next = merge(a->next, b);
    } else {
        h = b;
        h->next = merge(a, b->next);
    }
    return h;
}

当我运行程序并输入/打印一些值时，我得到：

9 4 32 2 6

然后，当我对其进行排序时，输出将变为：

9 4 2 6 32