C++でマージソートを用いて双方向連結リスト（双方向リンクリスト）をソートする方法

問題概要

双方向連結リスト（ダブリーリンクリスト）が与えられたとき、マージソート（merge sort）アルゴリズムを使って昇順に並べ替えます。

元のリスト: 10->20->8->17->5->13->4
ソート後のリスト: 4->5->8->10->13->17->20

双方向連結リストは各ノードが「前」と「次」へのポインタを持つため、通常の片方向リストと異なり、マージ処理の際に prev ポインタも正しく更新する 必要がある点に注意しましょう。

アルゴリズムの手順

1. 先頭ポインタが NULL、またはリストの要素数が1つだけなら、そのままリストを返す
2. 元のリストを前半と後半の2つのリストに分割する
3. 前半と後半それぞれを再帰的にソートする
4. ソート済みの2つのリストをマージ（統合）する

リストの中央を見つけるには、高速ポインタ（fast）と低速ポインタ（slow） を使う手法が有効です。fast が2ノード先へ進む間に slow を1ノードだけ進めることで、ループ終了時に slow が中央付近に到達します。

C++による実装例

#include <iostream>
#include <new>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

// 双方向連結リストのノード構造体
struct node {
    int data;
    struct node *next;
    struct node *prev;
};

// 配列から双方向連結リストを生成する関数
node *createList(int *arr, int n){
    node *head, *p, *q;
    p = head = new node;
    head->data = arr[0];
    head->prev = NULL;
    head->next = NULL;
    for (int i = 1; i < n; ++i) {
        q = new node;
        q->data = arr[i];
        q->prev = p;
        q->next = NULL;
        p->next = q;
        p = q;
    }
    return head;
}

// リストの内容を表示する関数
void displayList(node *head){
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

// ソート済み2つのリストをマージする関数（再帰）
node *mergeSortedLists(node *head1, node *head2){
    node *result = NULL;
    if (head1 == NULL) {
        return head2;
    }
    if (head2 == NULL) {
        return head1;
    }
    if (head1->data < head2->data) {
        head1->next = mergeSortedLists(head1->next, head2);
        head1->next->prev = head1;
        head1->prev = NULL;
        return head1;
    } else {
        head2->next = mergeSortedLists(head1, head2->next);
        head2->next->prev = head2;
        head2->prev = NULL;
        return head2;
    }
}

// fast/slow ポインタでリストを前後に分割する関数
void splitList(node *src, node **fRef, node **bRef){
    node *fast;
    node *slow;
    slow = src;
    fast = src->next;
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }
    *fRef = src;
    *bRef = slow->next;
    slow->next = NULL;
}

// マージソート本体（再帰）
void mergeSort(node **head){
    node *p = *head;
    node *a = NULL;
    node *b = NULL;
    if (p == NULL || p->next == NULL) {
        return;
    }
    splitList(p, &a, &b);
    mergeSort(&a);
    mergeSort(&b);
    *head = mergeSortedLists(a, b);
}

int main(){
    int arr[] = {10, 20, 8, 17, 5, 13, 4};
    node *head;
    head = createList(arr, SIZE(arr));
    cout << "Unsorted list: " << endl;
    displayList(head);
    mergeSort(&head);
    cout << "Final sorted list: " << endl;
    displayList(head);
    return 0;
}

実装のポイント

• createList: 配列の要素を順番に読み込み、prev/next ポインタを適切に設定しながら双方向連結リストを構築します。
• splitList: fast/slow の2つのポインタを使ってリストをほぼ半分に分割し、後半リストの先頭を返します。分割点では next を NULL にして前半リストを切り離します。
• mergeSortedLists: 再帰的に2つのソート済みリストを統合します。双方向リストなので、統合後の各ノードについて prev ポインタも忘れずに更新しているのが重要なポイントです。
• mergeSort: 分割→再帰ソート→マージの一連の流れを実行するメインの再帰関数です。

実行結果

上記プログラムをコンパイルして実行すると、以下の出力が得られます。

Unsorted list:
10 20 8 17 5 13 4
Final sorted list:
4 5 8 10 13 17 20

計算量について

マージソートの時間計算量は、要素数を n とすると O(n log n) です。リストを半分ずつに分割する操作が O(log n) 回発生し、それぞれの段階でのマージ処理に O(n) かかるためです。また、クイックソートと異なりデータの初期配置に依存せず常に安定した性能を発揮するため、連結リストのソートには特に適したアルゴリズムと言えます。