Algorithm Gymnastics 16

Merge Sort Merge sort is one of the famous sorting algorithms that uses divide & conquer. It is a sorting algorithm that tries to realize sorting by recursively dividing and merging again. This time I would like to use that merge sort to sort the Linked List instead of the array.

Example

Solution

Runtime Complexity O(n(log(n)) It takes proportional to n to merge with n lists. (merge) Also, it takes log (n) time to divide n pieces of data into two pieces. (divide) Therefore, the execution time is O (n log (n)). Memory Complexity O（log n) Using recursion consumes memory on the stack, resulting in O (log n).

The split step splits the entered list in half and continues with a list of size 1 or 0. The join step merges the sorted lists and continues until the lists are completely sorted. The recursive relationship of this merge sort algorithm is as follows:

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

This formula is used when analyzing the Runtime Complexity of the recursion algorithm, and is used in university classes, etc. Since it is a content to be dealt with, I will not go into that much, but if you are interested, click here Reference.

Way of thinking

Since merge sort is performed on the list instead of the array, the links of adjacent nodes when splitting I will cut it. Then, it feels like comparing one node with each other and merging them while sorting. The implementation may be a bit confusing as it uses recursion. The idea is that there are three methods. The first mergeSort method builds a rough logic frame divide & merge. Then, the second splitHalf method is the divide, which has the role of splitting the Link. Put the heads of the two split lists in the pair object. And the third mergeSortedList method is the merge role, which is responsible for merging and rearranging the split nodes.

Implementation

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 Sorted like this!