Sort a Linked List using Merge Sort

Sorting a Linked list question appears very often in coding interviews. Here, we will explore one of the most efficient ways of sorting a Linked list - using Merge sort.

We've already covered the Merge sort in one of the previous posts. 

Here, we will apply the same logic, just on the Linked list.

Note: We will be using our own implementation of the LinkedList class. We already implemented it from scratch here.

In this post, we'll add the sort method to our LinkedList class and a couple of helper private methods.

Merge sort a Linked list in Java implementation

Let's first implement the main part - the mergeSort method:

public void sort() {
    head = mergeSort(head);
}

public Node<T> mergeSort(Node<T> head) {
    if (head == null || head.next == null) {
        return head;
    }

    Node<T> middle = findMiddle(head);
    Node<T> middleNext = middle.next;
    middle.next = null; // break the connection between two lists
    Node<T> left = mergeSort(head);
    Node<T> right = mergeSort(middleNext);
    return (Node<T>) merge((Node<Integer>) left, (Node<Integer>) right);
}

Here, we first find the middle node, save the next node in a new variable middleNext and then set the middle.next to null, to break the connection between the two lists.

Then we do the same for the left part (starting from the head node) and the right part (starting from the middle.next node)

At the end, we call the merge method to merge two sorted linked lists providing the head nodes of both lists).

Here is the findMiddle(Note<T> head) method:

public Node<T> findMiddle(Node<T> head) {
    if (head == null) {
        throw new RuntimeException("The list is empty!");
    }

    Node<T> fast = head;
    Node<T> slow = head;
    int i = 0;

    while (fast.next != null) {
        fast = fast.next;
        i++;

        // if true - it means we moved the fast node two times, now move the slow node
        if (i % 2 == 0) {
            slow = slow.next;
        }
    }

    return slow;
}

This method finds the middle element. We covered this part in a separate post.

And here is the merging part - where we merge to sorted linked lists:

    public Node<Integer> merge(Node<Integer> left, Node<Integer> right) {
        Node<Integer> resultNode = null;

        if(left == null) {
            return right;
        }

        if(right == null) {
            return left;
        }

        if(left.data <= right.data) {
            resultNode = left;
            resultNode.next = merge(left.next, right);
        } else {
            resultNode = right;
            resultNode.next = merge(left, right.next);
        }

        return resultNode;
    }
}

Here, we've used a recursion to traverse through both linked lists and we used the resultNode to build a new sorted Linked List out of the two lists that we got as inputs.

The time and space complexity is O(n log n) since this is a divide-and-conquer algorithm.

This is all about how to sort a Linked list using Merge sort. 
For more on this subject, check out this GFG post.