singly linked list sort routines (selection sort, insertion sort, merge sort)

sort_single_linked_list.cpp

#include <iostream>
using namespace std;


struct node {
    int info;
    node* next;
    node(int i = 0, node* n = nullptr) : info(i), next(n) { }
};

void print(node* head) {
    for (node* t = head; t != nullptr; t = t->next) {
        cout<<t->info<<" ";
    }
    cout<<endl;
}

node* removeMax(node* head, node** max) {
    if (head == nullptr)
        return head;
    if (head->info > (*max)->info) {
        *max = head;
    }
    head->next = removeMax(head->next, max);
    if (head == *max) {
        head = head->next;
        return head;
    }
    return head;
}

node* insertSorted(node* list, node* x) {
    if (list == nullptr)
        return x;
    if (x->info > list->info)
        list->next = insertSorted(list->next, x);
    else {
        x->next = list;
        list = x;
    }
    return list;
}

node* selectionSort(node* list) {
    node* sorted = nullptr;
    while (list != nullptr) {
        node* max = list;
        list = removeMax(list, &max);
        max->next = sorted;
        sorted = max;
    }
    return sorted;
}

node* insertionSort(node* list) {
    node* sorted = nullptr;
    while (list != nullptr) {
        node* x = list;
        list = list->next;
        x->next = nullptr;
        sorted = insertSorted(sorted, x);
    }
    return sorted;
}

node* merge(node* a, node* b) {
    node d(0, nullptr); node* c = &d;
    while (a != nullptr && b != nullptr) {
        if (b->info > a->info) {
            c->next = a; a = a->next; c = c->next;
        } else {
            c->next = b; b = b->next; c = c->next;
        }
    }
    c->next = (a == nullptr) ? b:a;
    return d.next;
}

node* mergesort(node* list) {
    if (list == nullptr || list->next == nullptr)
        return list;
    node *slow = list, *fast = list->next;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    node *front = list, *back = slow->next;
    slow->next = nullptr;
    return merge(mergesort(front), mergesort(back));
}