Merge Sort

병합 정렬은 정렬 알고리즘 중에서도 divide&conquer를 사용한 유명한 하나군요.
재귀적으로 분할해 가고, 다시 병합(병합)해 가는 것으로, 재정렬을 실현하려고 하는, 소트 알고리즘입니다.
이번에는 그 병합 정렬을 사용하여 배열이 아닌 링크 된 목록을 정렬하고 싶습니다.

예

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

이런 느낌으로 정렬되었습니다!