Sort Linked Lists in C++ with Merge Sort

A C++ program can have a chain of nodes that needs sorting before you use its values. A singly linked list stores each value in a node linked to the next, and merge sort orders those nodes by reconnecting them in ascending order.

I’ll explain how the pointers split the list and show the sorted output from the complete C++ program.

TL;DR

Merge sort arranges a singly linked list in ascending order by splitting its links into smaller runs, sorting those runs and joining them in order. The approach takes O(n log n) time and changes the links instead of shifting array elements.

• Use slow and fast pointers to cut the list near its midpoint.
• Stop recursion when a run has zero or one node.
• Merge by linking the smaller front node, choosing the left node on equal values.
• Expect O(log n) auxiliary call-stack space in this recursive version.

What is a linked list?

A singly linked list is a sequence of nodes where each node stores a value and a pointer to the next node. The head pointer identifies the first node, and the final node points to nullptr.

Unlike an array, a linked list does not provide direct indexing to its middle element. Reaching a node means following next pointers from the head, so an algorithm that repeatedly swaps distant indexed elements is a poor fit.

Merge sort works by sequential traversal. It divides the chain into shorter runs, sorts each run and reconnects existing nodes in order. That keeps the main operation focused on pointer links rather than allocating a second array of values.

For a standard-library std::list, use values.sort() rather than trying std::sort(values.begin(), values.end()). std::sort requires random-access iterators, while list iterators do not provide them. The member sort also keeps the operation attached to the container that owns the nodes.

A custom Node type exposes the mechanics behind this example. When the application already stores records in std::list, its member function avoids custom pointer manipulation.

How to sort a linked list in C++ step by step

The implementation has three linked operations: create nodes, split a chain, and merge sorted chains. Keeping the split and merge helpers separate makes each pointer boundary clear.

Step 1: Build the singly linked list

Each Node holds an integer and a next pointer. The example’s makeList() helper connects each new node after the previous one, so the input order is preserved before sorting begins.

struct Node {
    int value;
    Node* next;
    explicit Node(int v) : value(v), next(nullptr) {}
};

A null next pointer marks the end of the chain. The complete program later includes a destructor loop that deletes every allocated node after printing, so the sample also shows who owns this memory.

Step 2: Split it with slow and fast pointers

Start slow at the head and fast at the second node. Advancing slow once for every two fast steps leaves slow at the final node of the left half. Starting fast one node ahead makes the cut split an even-length list into equal halves.

Node* slow = head;
Node* fast = head->next;
while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
}
Node* right = slow->next;
slow->next = nullptr;

After the cut, head still points to the left run and right points to the new right run. Setting slow->next to nullptr is the boundary that prevents recursive calls from seeing the original unsplit chain again. For three nodes, the left run has two nodes and the right run has one, which still guarantees progress toward the base case.

Step 3: Merge the sorted halves

Once each half is sorted, compare their front values and attach the smaller node to a temporary tail. Move forward only in the half that supplied that node. When either run ends, attach the other run as-is.

Node* merge(Node* left, Node* right) {
    Node dummy(0);
    Node* tail = &dummy;
    while (left && right) {
        if (left->value <= right->value) {
            tail->next = left;
            left = left->next;
        } else {
            tail->next = right;
            right = right->next;
        }
        tail = tail->next;
    }
    tail->next = left ? left : right;
    return dummy.next;
}

The dummy node avoids a separate branch for choosing the first output node. It is only a local helper, not part of the returned list. Using less-than-or-equal means equal values from the left run stay before equal values from the right run, preserving their original order across the split.

Step 4: Run the complete program

The function returns the new head, which may differ from the input head after sorting. Assign the return value back to head before traversing or deleting the list.

#include <iostream>
#include <vector>

struct Node {
    int value;
    Node* next;
    explicit Node(int v) : value(v), next(nullptr) {}
};

Node* merge(Node* left, Node* right) {
    Node dummy(0);
    Node* tail = &dummy;
    while (left && right) {
        if (left->value <= right->value) {
            tail->next = left;
            left = left->next;
        } else {
            tail->next = right;
            right = right->next;
        }
        tail = tail->next;
    }
    tail->next = left ? left : right;
    return dummy.next;
}

Node* mergeSort(Node* head) {
    if (!head || !head->next) return head;
    Node* slow = head;
    Node* fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    Node* right = slow->next;
    slow->next = nullptr;
    return merge(mergeSort(head), mergeSort(right));
}

Node* makeList(const std::vector<int>& values) {
    Node dummy(0);
    Node* tail = &dummy;
    for (int value : values) {
        tail->next = new Node(value);
        tail = tail->next;
    }
    return dummy.next;
}

void printList(const Node* node) {
    while (node) {
        std::cout << node->value;
        node = node->next;
        if (node) std::cout << " -> ";
    }
    std::cout << '\n';
}

void destroyList(Node* node) {
    while (node) {
        Node* next = node->next;
        delete node;
        node = next;
    }
}

int main() {
    const std::vector<int> input{5, 8, 6, 7, 10, 1, 4};
    Node* head = makeList(input);
    std::cout << "Input:  ";
    printList(head);
    head = mergeSort(head);
    std::cout << "Sorted: ";
    printList(head);
    destroyList(head);
}

I compiled this source with g++ using C++17 and the -Wall, -Wextra and -pedantic warnings, then ran the resulting executable. It printed the original chain followed by the ascending chain:

Input:  5 -> 8 -> 6 -> 7 -> 10 -> 1 -> 4
Sorted: 1 -> 4 -> 5 -> 6 -> 7 -> 8 -> 10

The output has the same seven values as the input, in ascending order. The command in the terminal image is the same executable built from the complete source above.

Edge cases and complexity

Merge sort takes O(n log n) time because each split level processes all n nodes during merging, and balanced splitting creates about log n levels. The recursive implementation uses O(log n) auxiliary stack space for those calls, in addition to the input nodes.

Never use a value such as -1 to signal the end of input when -1 may be a valid list element. The example builds from a vector, so every integer remains data. An interactive program should read until end-of-file or use a separate explicit count instead of reserving one value.

The recursion stops because every split creates two shorter lists, including when the original count is odd. A failed cut that leaves the entire list on one side causes unbounded recursion, so the assignment to slow->next is part of correctness, not an optional cleanup.

For very long chains or a strict constant-stack requirement, use a bottom-up merge sort that merges runs of increasing width without recursive calls. The recursive version shown here does not meet a strict O(1) auxiliary-space requirement, even though it reuses the original nodes. A conversion to std::vector followed by std::sort can be simpler when extra storage is acceptable and random access is useful for later work.

For a production list, the comparator may inspect a key inside a larger record rather than compare integers. Keep that comparison consistent, choosing the left node whenever its key should precede or equal the right key. A comparator that changes its answer for the same pair can break the assumptions that make merging correct.

Sorting also changes the node links, not the objects that own the chain. After mergeSort() returns, discard stale assumptions about which node is first and store the returned head. Any external pointer to an individual node still points to that node, but its next pointer may now lead to a different successor.

If nodes are shared with another structure, relinking them can alter that other structure too. In that case, choose an explicit ownership model before sorting, or sort a separate sequence of pointers. This example owns each allocated node through one head pointer and deletes the chain only after sorting is finished.

The merge helper is iterative, so its own work does not add a recursive call for each compared pair. The divide-and-conquer calls set the depth. Each call handles a shorter half, keeping the stack proportional to the number of split levels.

Conclusion

To sort a custom singly linked list, split it into shorter chains and merge nodes back in order. Return the new head, handle empty input in the base case, and account for the recursive call stack when choosing this implementation.

For more on linked-list representation, see Programiz’s linked-list overview. The std::list::sort reference documents the standard container’s member sort for cases where a custom node type is unnecessary.

FAQ

These answers cover two common decisions when sorting a linked list in C++.