C++でマージソートを用いて連結リストをソートする方法

問題の概要

連結リスト（リンクリスト）が与えられたとき、マージソートのアルゴリズムを用いて昇順にソートします。

List: 10->20->8->17->5->13->4
Sorted list: 4->5->8->10->13->17->20

アルゴリズム

1. headがNULL、またはリストの要素数が1つだけの場合は、そのリストをそのまま返します。
2. 元のリストを中央で2分割し、2つのリストを作成します。
3. 前半と後半のリストをそれぞれ再帰的にソートします。
4. ソート済みの2つのリストをマージ（統合）します。

C++による実装例

以下は、C++で連結リストをマージソートによりソートする完全なサンプルコードです。リストの分割には「高速ポインタ（fast）」と「低速ポインタ（slow）」を用いる手法を採用しており、リストを効率的に中央で2分割できます。

#include <iostream>
#include <new>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
struct node {
   int data;
   struct node *next;
};
node *createList(int *arr, int n){
   node *head, *p;
   p = head = new node;
   head->data = arr[0];
   head->next = NULL;
   for (int i = 1; i < n; ++i) {
      p->next = new node;
      p = p->next;
      p->data = arr[i];
      p->next = NULL;
   }
   return head;
}
void displayList(node *head){
   while (head != NULL) {
      cout << head->data << " ";
      head = head->next;
   }
   cout << endl;
}
node *mergeSortedLists(node *head1, node *head2){
   node *result = NULL;
   if (head1 == NULL) {
      return head2;
   }
   if (head2 == NULL) {
      return head1;
   }
   if (head1->data < head2->data) {
      result = head1;
      result->next = mergeSortedLists(head1->next,head2);
   } else {
      result = head2;
      result->next = mergeSortedLists(head1, head2->next);
   }
   return result;
}
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;
}

コードのポイント

splitList関数では、slowポインタを1つずつ、fastポインタを2つずつ進めることで、fastがリストの末尾に到達した時点でslowがちょうど中央に位置するようになります。これにより、リストを前半と後半に分割できます。

mergeSortedLists関数は再帰的に呼び出され、2つのソート済みリストの先頭要素を比較しながら小さい方からつなげていくことで、昇順の1つのリストに統合します。

mergeSort関数は、リストを分割→再帰的にソート→マージ、という流れを要素数が1以下になるまで繰り返す本体部分です。

出力結果

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

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

計算量について

マージソートの時間計算量はO(n log n)です。連結リストの場合、配列と異なり要素の物理的な移動が不要で、追加のメモリ領域もほとんど必要としないため、連結リストのソートに特に適したアルゴリズムといえます。