Sort a Linked List (Merge Sort)

Given, a pointer to the head of a singly linked list, sort the linked list such that all nodes are arranged in non-decreasing order of their node values.

Sorting a linked list

Algorithm:

We have already discussed Merge Sort on arrays. The approach will be similar in the case of linked lists as well.

1. Recursively Divide the list into two havles
2. Sort the two smaller halves.
3. Merge the two halves back together.

We have also discussed how to find the middle node in a singly linked list. 
The find middle node function will help us divide the linked list into two halves.

Once the linked list is divided into two halves, we need to sort the sub-linked lists and merge them back together using the merging function.
We will use a dummy node method to store the intermediate merged linked list whose head will be returned as result.

Code in Python: 

# Python program to perform Merge Sort on a Signly linked list


# Node class
class Node:

    # Constructor to initialise data and next
    def __init__(self, data=None):
        self.data = data
        self.next = None


class SinglyLinkedList:

    # Constructor to initialise head
    def __init__(self, head=None):
        self.head = head

    # Function to Insert data at the beginning of the linked list
    def insert_at_beg(self, data):
        node = Node(data)
        node.next = self.head
        self.head = node

    # Function to print the linked list
    def print_data(self):
        current = self.head
        while current is not None:
            print(current.data, '-> ', end='')
            current = current.next
        print('None')


# Function to split the linked list into two halves
def split(head):
    slow = head

    if slow is None or slow.next is None:
        return head, None

    fast = slow.next

    # Reach to the middle of the linked list
    while fast is not None:
        fast = fast.next
        if fast is not None:
            fast = fast.next
            slow = slow.next

    fast = slow.next
    # break the linked list in half
    slow.next = None

    # return the 2 linked lists formed
    return head, fast


# Function to merge linked lists in sorted order
def merge(a, b):
    # Make a dummy node
    dummy = Node()
    # dummy node next will be the head of our merged list
    dummy.next = None

    temp = SinglyLinkedList(dummy)
    tail = temp.head

    while True:
        if a is None:
            tail.next = b
            break
        elif b is None:
            tail.next = a
            break
        elif a.data <= b.data:
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next

    return temp.head.next


# Function Merge Sort
def merge_sort(head):

    if head is None or head.next is None:
        return head

    a, b = split(head)
    a = merge_sort(a)
    b = merge_sort(b)

    head = merge(a, b)

    return head

linked_list = SinglyLinkedList()
linked_list.insert_at_beg(9)
linked_list.insert_at_beg(3)
linked_list.insert_at_beg(2)
linked_list.insert_at_beg(1)
linked_list.insert_at_beg(5)
linked_list.insert_at_beg(4)
linked_list.insert_at_beg(8)
linked_list.insert_at_beg(7)
linked_list.insert_at_beg(6)
# before sorting
print('before sorting')
linked_list.print_data()
# call merge_sort function
linked_list.head = merge_sort(linked_list.head)
# after sorting
print('after sorting')
linked_list.print_data()

"""
Outputs:
before sorting
6 -> 7 -> 8 -> 4 -> 5 -> 1 -> 2 -> 3 -> 9 -> None
after sorting
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> None
"""

In this code, merge_sort() function is called to split() the linked list into two halves, a and b. Then, merge_sort is applied on the two split halves.

This process is repeated recursively until there is only one node left in each sub lists.

Then the merge(a, b) function is called to merge the linked lists together in sorted order.

The merge(a, b) function keeps on adding nodes from either a or b depending on the node value until one of the linked lists end. The remaining linked list is added completely to the tail.

The head of this temporary linked list is returned by the merge(a, b) function.

Time Complexity:

The algorithm just like merge sort on arrays takes O(n log n) time to sort the arrays.

Que. Why not use QuickSort or HeapSort?

Ans. QuickSort and HeapSort require random access of elements and jumping to and fro in the data structure which is not possible in linked lists as the address of the nodes are not known. Hence these algorithms would not be efficient to implement on a linked list.

--
Have any questions or suggestions? Post in the comments below!!

By,
Anubhav Shrimal