Linked List Part 4: Sorting Using Merge Sort

Sorting linked lists efficiently can be quite challenging, particularly when compared to arrays. Unlike arrays, linked lists do not support direct access to elements by index, which makes some sorting algorithms less effective. One of the most efficient ways to sort a linked list is by using Merge Sort, a divide-and-conquer algorithm that is well-suited for this data structure.

Overview of Merge Sort

Merge Sort works by recursively dividing the list into smaller sub lists, sorting those sub lists, and then merging them back together in a sorted manner. The process can be broken down into three main steps:

1. Splitting: Divide the linked list into two halves.
2. Sorting: Recursively sort each half.
3. Merging: Merge the two sorted halves back together.

Let's dive into the details of how to implement Merge Sort on a linked list.

Method: sort()

This method initiates the merge sort process on the linked list. It is the entry point for sorting the list.

/* Sort Linked list -  Use Divide and Conquer algorithm for a merge sort */
    public void sort(){
       this.head = mergeSort(this.head);
       
       //udpate tail value
       this.tail = this.travelToTail(); 
    }

• Purpose: Sort the entire linked list.
• Implementation: Calls the mergeSort method to sort the list starting from the head. After sorting, it updates the tail of the list to ensure it correctly points to the last element.
• travelToTail is explained on the next post. Linked List Part 5: Rotation

Method: mergeSort(Node head)

This method performs the actual merge sort on the linked list.

/* Implementation of merge sort for a linked list */
    protected Node mergeSort(Node head){
        //if head or next is null return the head, 
        // this means that the linked list is already sorted
        if(head == null || head.next == null){
            return head;
        }
        //Split the linked list on middle
        Node left = head; 
        Node right = this.getMidNode(head); 
        Node temp = right.next; 
        right.next = null;
        right = temp;
        left = this.mergeSort(left);
        right = this.mergeSort(right);
        return this.mergeSortedList(left, right);
        
    }

• Purpose: Recursively sort the linked list.
• Implementation:
  • Base Case: If the list is empty or contains only one element, it is already sorted.
  • Splitting: Uses getMidNode to find the middle of the list, splits the list into two halves.
  • Recursive Sorting: Calls mergeSort on both halves.
  • Merging: Uses mergeSortedList to merge the sorted halves.

Method: getMidNode(Node head)

This method finds the middle node of the linked list.

protected Node getMidNode (Node head){
        if (head == null) {
            return head;
        }
         
        Node slow = head;
        Node fast = head; 
        while (fast.next != null && fast.next.next != null){ 
            slow = slow.next; 
            fast = fast.next.next; 
        } 
    
        return slow;   
    }

• Purpose: Find the middle node of the list to split it into two halves.
• Implementation: Uses two pointers, slow and fast. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. When fast reaches the end of the list, slow will be at the midpoint.

Method: mergeSortedList(Node left, Node right)

This method merges two sorted linked lists into a single sorted linked list.

private Node mergeSortedList (Node left, Node right){
        Node result = null;
        if(left == null){
            return right;
        }
        if(right == null){
            return left;
        }
        if(left.data > right.data){
            result = right;
            result.next = mergeSortedList(left, right.next);
        }else{
            result = left;
            result.next = mergeSortedList(left.next, right);
        }
        return result;
    }

• Purpose: Merge two sorted linked lists into one sorted list.
• Implementation:
  • Base Case: If one list is empty, return the other list.
  • Recursive Merging: Compare the data of the nodes from the two lists and recursively merge the rest.

Time and Space Complexity

• Time Complexity: O(n log n), where n is the number of nodes in the linked list. The list is divided into halves, and each level of recursion performs a linear merge.
• Space Complexity: O(log n) due to recursion stack space. The space complexity is not dependent on the size of the list but on the recursion depth.

Conclusion

Merge Sort is a highly efficient algorithm for sorting linked lists, leveraging its divide-and-conquer strategy. By dividing the list into smaller parts, sorting them recursively, and merging them, Merge Sort ensures a time complexity of O(n log n), making it suitable for large lists. The ability to handle the list in-place with minimal extra space makes Merge Sort an excellent choice for linked list sorting tasks.

Next: Rotating Linked List by k elements.