C++で連結リストをマージソートする方法｜実装手順とサンプルコード

マージソートは「分割統治法（divide and conquer）」に基づくソートアルゴリズムです。データセット全体を小さな部分に分割していき、それぞれを整列させながら大きな塊へと統合することで、最終的に完全にソートされたデータを得ます。最悪ケースでも時間計算量が O(n log n) と低く抑えられるため、入力データの初期状態に左右されず安定した性能を発揮できるのが大きな特徴です。

連結リスト（リンクリスト）は、マージソートとの相性が抜群です。配列のように要素を物理的に移動させる必要がなく、ノード間のリンク（ポインタ）を付け替えるだけでマージ処理が完結するため、非常に効率的にソートできます。ここでは、この手法を用いて連結リストをソートする方法を詳しく解説します。

マージソートの計算量

• 時間計算量 − すべてのケースで O(n log n)

• 空間計算量 − O(n)

入力 − ソート前のリスト：14 20 78 98 20 45
出力 − ソート後のリスト：14 20 20 45 78 98

アルゴリズム

mergeList(ll1, ll2)

入力 − ソート済みの2つの連結リスト ll1 と ll2

出力 − 統合された1つの連結リスト

Begin
   if ll1 is empty, then
      return ll2
   if ll2 is empty, then
      return ll1
   if data(ll1) <= data(ll2), then
      new_head = ll1;
      next(new_head) = mergeList(next(ll1), ll2)
   else
      new_head = ll2;
      next(new_head) = mergeList(ll1, next(ll2))
   return new_head
End

splitList(start, ll1, ll2)

入力 − 連結リストの先頭ポインタ start、および出力用引数 ll1 と ll2

出力 − 元のリストを半分に分割して得られる2つの連結リスト

Begin
   slow := start
   fast := next(start)
   while fast is not null, do
      fast := next(fast)
      if fast is not null, then
         slow := next(slow)
         fast := next(fast)
   end while
   ll1 := start
   ll2 := next(slow)
   next(slow) := null
End

splitList では「遅いポインタ（slow）」と「速いポインタ（fast）」の2つのポインタを使用します。fast が2ノード進む間に slow は1ノードしか進まないため、fast がリストの末端に到達した時点で slow はちょうど中央付近に位置しています。これにより、リストを前半と後半の2つにきれいに分割できます。

mergeSort(start)

入力 − ソート対象の連結リスト

出力 − ソート済みの連結リスト

Begin
   head = start
   if head is null or next(head) is null, then
      return
   split_list(head, ll1, ll2)
   mergeSort(ll1)
   mergeSort(ll2)
   start := mergeList(ll1, ll2)
End

C++による実装

#include<bits/stdc++.h>
using namespace std;
class node { // データと次ノードへのアドレスを保持するノードの定義
    public:
    int data;
    node *next;
};
void display(class node* start) {
    node* p = start; // 現在のノードを先頭に設定
    while(p != NULL) { // NULLになるまで走査
        cout << p -> data << " ";
        p = p -> next; // 次のノードへ移動
    }
}
node* getNode(int d) {
    node* temp = new node;
    temp -> data = d;
    temp -> next = NULL;
    return temp;
}
node* mergeList(node* ll1, node* ll2) { // 2つのソート済みリストを統合する関数
    node* newhead = NULL;
    if(ll1 == NULL)
        return ll2;
    if(ll2 == NULL)
        return ll1;
    // リストを再帰的にマージ
    if(ll1 -> data <= ll2 -> data) {
        newhead = ll1;
        newhead -> next = mergeList(ll1->next,ll2);
    } else {
        newhead = ll2;
        newhead -> next = mergeList(ll1,ll2->next);
    }
    return newhead;
}
void splitList(node* start, node** ll1,node** ll2) {
    // フロイドの循環検出法（ウサギとカメ）と同じ考え方
    node* slow = start;
    node* fast = start -> next;
    while(fast!= NULL) {
        fast = fast -> next;
        if(fast!= NULL) {
            slow = slow -> next;
            fast = fast -> next;
        }
    }
    *ll1 = start;
    *ll2 = slow -> next;
    // ここでリストを分割
    slow -> next = NULL;
}
void mergeSort(node** start) {
    node* head = *start;
    node* ll1,*ll2;
    // ベースケース
    if(head == NULL || head->next == NULL) {
        return;
    }
    splitList(head,&ll1,&ll2); // リストを前半と後半に分割
    // 左右の部分リストをそれぞれソート
    mergeSort(&ll1);
    mergeSort(&ll2);
    // 2つのソート済みリストをマージ
    *start = mergeList(ll1,ll2);
    return;
}
int main() {
   cout << "連結リストを作成します：" << endl;
   cout << "0を入力すると構築を終了します。それ以外は整数を入力してください" << endl;
   int k,count = 1,x;
   node* curr,*temp;
   cin >> k;
   node* head = getNode(k);   // リスト構築、最初のノード
   cin >> k;
   temp = head;
   while(k) {
      curr = getNode(k);
      temp -> next = curr;// 各ノードを末尾に追加
      temp = temp -> next;
      cin >> k;
   }
   cout<<"ソート前：" << endl;
   display(head); // リストを表示
   cout<<"\nソート後：" << endl;
   mergeSort(&head);
   display(head);
   return 0;
}

実行結果

連結リストを作成します：
0を入力すると構築を終了します。それ以外は整数を入力してください
89
54
15
64
74
98
10
24
26
0
ソート前：
89 54 15 64 74 98 10 24 26
ソート後：
10 15 24 26 54 64 74 89 98

まとめ

このプログラムでは、まず splitList 関数が slow と fast の2つのポインタによってリストをほぼ半分に分割し、mergeSort が再帰的に各部分リストをソートします。最後に mergeList が2つのソート済みリストを1つに統合して処理が完了します。要素のコピーや移動が不要でリンクの付け替えだけで済むため、連結リストのソートにはクイックソートよりもマージソートの方が適しているといえます。