アルゴリズム 体操16

Merge Sort

マージソートはソートアルゴリズムの中でもdivide&conquerを使った有名な一つですね。
再帰的に分割していき、再び併合（マージ）していくことで、並び替えを実現しようとする、ソートアルゴリズムです。
今回はそのマージソートを使って配列ではなく、Linked Listをソートしてみたいと思います。

例

Solution

Runtime Complexity O(n(log(n))

n 個のリストとをマージするには n に比例した時間がかかります。(merge)
また、n 個のデータを1個ずつになるまで2分割していくには log(n) 時間がかかります。(divide)
したがって、実行時間は O(n log(n)) となります。

Memory Complexity O（log n)

再帰を使うと、スタック上のメモリを消費するため、O（log n）となります。

分割ステップでは、入力されたリストを2つに半分に分割し、サイズが1または0のリストになるで続けます。
結合ステップでは、ソートされたリストをマージし、リストが完全にソートされるまでそれを続けます。
このマージソートアルゴリズムの再帰関係は次のようになります。

T（n）= 2T（n / 2）+ n

この式は再帰のアルゴリズムのRuntime Complexity を分析する時に使わて、大学の授業などで
扱われる内容なのでそこまで深入りはしないことにしますが興味がある方はこちらを参考にして下さい。

考え方

配列ではなく、リストに対してマージソートをするので、分割する際に隣り合うノードのリンクを
切っていきます。それから、一つのノード同士を比較してマージしながら並び替えていく感じです。
再帰を使っているので実装は少し分かりにくいかもしれません。アイデアはまず、三つのメソッドがあります。
一つ目のmergeSortメソッドで大まかなロジックフレームのdivide&mergeを組みます。
それから、二つ目のsplitHalfメソッドはdivide役で、Linkを分割する役割があり、
pairオブジェクトに分割した二つのリストのheadを入れておきます。
そして三つ目のmergeSortedListメソッドはmerge役で、分割されたノードをマージして並びかえていく責任を果たします。

実装

MergeSort.java

class MergeSort{

    public LinkedListNode mergeSort(LinkedListNode head) {

      // base case
      if (head == null || head.next == null) {
        return head;
      }

      Pair<LinkedListNode, LinkedListNode> pair = new Pair<LinkedListNode, LinkedListNode>(null, null);

      // Let's split the list in half, sort the sublists
      // and then merge the sorted lists.

      splitHalf(head, pair);

      pair.first = mergeSort(pair.first);
      pair.second = mergeSort(pair.second);

      return mergeSortedList(pair.first, pair.second);
  }
    // this method splits linked list in two halves by iterating over whole list
    // It returns head pointers of first and 2nd halves of linked lists in pair
    // Head of 1st half is just the head node of linked list
   public void splitHalf(LinkedListNode head, Pair<LinkedListNode, LinkedListNode> pair) {

      if (head == null) {
        return;
      }

      if (head.next == null) {
        pair.first = head;
        pair.second = null;
      } else {

        LinkedListNode slow = head;
        LinkedListNode fast = head.next;

      // Two pointers, 'fast' and 'slow'. 'fast' will move two steps in each 
      // iteration whereas 'slow' will be pointing to the middle element
      // at the end of the loop
        while (fast != null) {

          fast = fast.next;

          if(fast != null) {
            fast = fast.next;
            slow = slow.next;
          }
        }

        pair.first = head;
        pair.second = slow.next;

        // disconnecting the first linked list with the second one
        slow.next = null;
      }
    }
    public LinkedListNode mergeSortedList(LinkedListNode first, LinkedListNode second) {

      if (first == null) {
        return second;
      }

      if (second == null){
        return first;
      }

      LinkedListNode newHead;

      if (first.data <= second.data) {
        newHead = first;
        first = first.next;
      } else {
        newHead = second;
        second = second.next;
      }

      LinkedListNode current = newHead;

      while (first != null && second != null) {
        LinkedListNode temp = null;
        if (first.data <= second.data) {
          temp = first;
          first = first.next;
        } else {
          temp = second;
          second = second.next;
        }

        current.next = temp;
        current = current.next;
      }

      if (first != null) {
        current.next = first;
      } else if (second != null) {
        current.next = second;
      }

      return newHead;
    }
}

Output

こんな感じにソートされました！