Introduction

Merge sort is one of the best sorting algorithms for linked lists because it does not require random access. On a doubly linked list, it is especially convenient because nodes can be split and merged by rewiring pointers instead of copying array elements.

Why Merge Sort Fits Linked Lists

Array-based sorts often depend on indexing into the middle of the structure or moving many elements around. Linked lists are not good at either of those things. Merge sort, by contrast, only needs:

• a way to split the list into halves
• a way to merge two already-sorted lists

Both operations are natural on linked lists.

The overall complexity remains O(n log n), and merge sort is stable when implemented carefully. That means equal elements keep their original relative order, which can matter when nodes store records with secondary meaning.

Core Steps

Sorting a doubly linked list with merge sort follows the same high-level recipe as array merge sort:

1. find the middle of the list
2. split the list into two halves
3. recursively sort each half
4. merge the two sorted halves

The main difference is pointer maintenance. Because this is a doubly linked list, both next and prev pointers must stay consistent after every merge.

C++ Implementation

The following example sorts a doubly linked list of integers.

1#include <iostream>
2
3struct Node {
4    int value;
5    Node* prev;
6    Node* next;
7
8    explicit Node(int v) : value(v), prev(nullptr), next(nullptr) {}
9};
10
11Node* split(Node* head) {
12    Node* slow = head;
13    Node* fast = head;
14
15    while (fast->next && fast->next->next) {
16        slow = slow->next;
17        fast = fast->next->next;
18    }
19
20    Node* second = slow->next;
21    slow->next = nullptr;
22    if (second) {
23        second->prev = nullptr;
24    }
25    return second;
26}
27
28Node* merge(Node* first, Node* second) {
29    if (!first) return second;
30    if (!second) return first;
31
32    if (first->value <= second->value) {
33        first->next = merge(first->next, second);
34        if (first->next) {
35            first->next->prev = first;
36        }
37        first->prev = nullptr;
38        return first;
39    } else {
40        second->next = merge(first, second->next);
41        if (second->next) {
42            second->next->prev = second;
43        }
44        second->prev = nullptr;
45        return second;
46    }
47}
48
49Node* mergeSort(Node* head) {
50    if (!head || !head->next) {
51        return head;
52    }
53
54    Node* second = split(head);
55
56    head = mergeSort(head);
57    second = mergeSort(second);
58
59    return merge(head, second);
60}
61
62void printList(Node* head) {
63    for (Node* cur = head; cur != nullptr; cur = cur->next) {
64        std::cout << cur->value << ' ';
65    }
66    std::cout << '\n';
67}
68
69void pushFront(Node*& head, int value) {
70    Node* node = new Node(value);
71    node->next = head;
72    if (head) {
73        head->prev = node;
74    }
75    head = node;
76}
77
78int main() {
79    Node* head = nullptr;
80    pushFront(head, 3);
81    pushFront(head, 1);
82    pushFront(head, 5);
83    pushFront(head, 2);
84    pushFront(head, 4);
85
86    head = mergeSort(head);
87    printList(head);
88}

This code shows the essential pieces: split, recursive sort, and merge.

The Split Step Matters

The slow-and-fast pointer technique is the standard way to find the midpoint of a linked list. Once the middle is found, the list is cut into two independent sublists.

The important detail in a doubly linked list is not just slow->next = nullptr, but also resetting the second half's prev pointer to nullptr. If you forget that step, the list may still sort partially, but backward traversal will be broken.

The Merge Step Must Repair Both Directions

When merging, many implementations remember to set next and forget to repair prev. That leads to a list that looks fine when printed forward but fails when traversed backward or when later operations rely on prev links.

A correct merge does three things repeatedly:

• chooses the smaller head node
• links its next pointer to the merged remainder
• repairs the chosen remainder's prev pointer back to the current node

That is the doubly linked list version of merge sort in one sentence.

Common Pitfalls

• Splitting the list without clearing the second half's prev pointer.
• Merging correctly in the forward direction but leaving backward links broken.
• Forgetting the base case for empty and one-node lists.
• Accidentally creating cycles by reusing old pointers after splitting.
• Using data swapping instead of pointer rewiring when the real goal is to sort nodes structurally.

Summary

• Merge sort is a strong fit for doubly linked lists because it works through pointer manipulation rather than indexing.
• The algorithm runs in O(n log n) time and is stable when implemented carefully.
• Use slow and fast pointers to split the list into halves.
• During merging, maintain both next and prev links correctly.
• Always test forward traversal and backward traversal after sorting.