Merge Sort on Linked List 🎯

Welcome to our deep dive into the world of Merge Sort on Linked Lists! This lesson is designed to help you understand, implement, and master this powerful algorithm, all while keeping it simple and practical. By the end of this tutorial, you'll be able to sort any linked list using Merge Sort, a divide-and-conquer strategy that's efficient, easy to understand, and widely used in the tech industry.

Let's get started!

Introduction 📝

Before we dive into the heart of the matter, let's quickly recap what we already know. We're going to use a linked list and sort it using the Merge Sort algorithm. A linked list is a linear data structure where each element, called a node, consists of data and a reference (link) to the next node in the sequence.

Merge Sort Overview 💡

Merge Sort is a divide-and-conquer algorithm, which means it breaks down a problem into smaller sub-problems, solves them recursively, and then merges the solutions to obtain the final answer. The main advantage of Merge Sort is its efficient time complexity, O(n log n), making it a popular choice for sorting large data sets.

Merge Sort on Linked List 💡

Now, let's focus on how to apply Merge Sort to a linked list. The process involves dividing the list into two halves, sorting each half using Merge Sort, and then merging the sorted halves back together.

Algorithm Steps 📝

If the list has one or zero elements, it is already sorted, so return.
Find the middle of the list and divide it into two halves.
Recursively sort both halves using Merge Sort.
Merge the sorted halves back into a single sorted list.

Merging Sorted Halves 💡

Merging two sorted lists is the key step in the Merge Sort algorithm. We'll create a new list that combines the two sorted halves in the correct order.

Here's a high-level overview of the merging process:

Initialize three pointers, p1, p2, and pMerge, pointing to the first nodes of the two sorted halves and the new list, respectively.
Compare the values at p1 and p2. The smaller value gets appended to the new list.
Move the pointer of the node containing the smaller value forward (p1 or p2).
Repeat steps 2 and 3 until both halves are empty or one of them has reached the end.

Now that we've covered the theory, let's dive into some code examples!

Code Examples 💡

Example 1: Merge Sort on a Singly Linked List

Here's an implementation of the Merge Sort algorithm for a singly linked list in Python.

python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def merge(head1, head2):
    merge_head = Node(None)
    current_node = merge_head

    while head1 and head2:
        if head1.data <= head2.data:
            current_node.next = head1
            head1 = head1.next
        else:
            current_node.next = head2
            head2 = head2.next
        current_node = current_node.next

    if head1:
        current_node.next = head1

    if head2:
        current_node.next = head2

    return merge_head.next

def merge_sort(head):
    if not head or not head.next:
        return head

    mid = find_mid(head)
    left_half = head
    right_half = mid.next
    mid.next = None

    left_sorted = merge_sort(left_half)
    right_sorted = merge_sort(right_half)

    return merge(left_sorted, right_sorted)

def find_mid(head):
    slow_ptr = head
    fast_ptr = head

    while fast_ptr and fast_ptr.next and fast_ptr.next.next:
        slow_ptr = slow_ptr.next
        fast_ptr = fast_ptr.next.next

    return slow_ptr

# Test the Merge Sort function
head = Node(3)
head.next = Node(5)
head.next.next = Node(8)
head.next.next.next = Node(10)
head.next.next.next.next = Node(1)
head.next.next.next.next.next = Node(2)

sorted_list = merge_sort(head)

while sorted_list:
    print(sorted_list.data)
    sorted_list = sorted_list.next

Example 2: Merge Sort on a Doubly Linked List

Now, let's implement Merge Sort for a doubly linked list in Python.

python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

def merge(head1, head2):
    merge_head = Node(None)
    current_node = merge_head

    while head1 and head2:
        if head1.data <= head2.data:
            current_node.next = head1
            head1 = head1.next
        else:
            current_node.next = head2
            head2 = head2.next

        current_node = current_node.next
        current_node.prev = merge_head

    if head1:
        current_node.next = head1

    if head2:
        current_node.next = head2

    current_node = merge_head.next
    current_node.prev = None

    return merge_head.next

def merge_sort(head):
    if not head or not head.next:
        return head

    mid = find_mid(head)
    left_half = head
    right_half = mid.next
    mid.next = None
    mid.prev = None

    left_sorted = merge_sort(left_half)
    right_sorted = merge_sort(right_half)

    return merge(left_sorted, right_sorted)

def find_mid(head):
    slow_ptr = head
    fast_ptr = head

    while fast_ptr and fast_ptr.next and fast_ptr.next.next:
        fast_ptr = fast_ptr.next.next
        slow_ptr = slow_ptr.next

    return slow_ptr

# Test the Merge Sort function
head = Node(3)
head.prev = None
head.next = Node(5)
head.next.prev = head
head.next.next = Node(8)
head.next.next.prev = head.next
head.next.next.next = Node(10)
head.next.next.next.prev = head.next.next
head.next.next.next.next = Node(1)
head.next.next.next.next.prev = head.next.next.next

sorted_list = merge_sort(head)

while sorted_list:
    print(sorted_list.data)
    sorted_list = sorted_list.next

Quiz Time 🎯

Conclusion 📝

Congratulations on mastering Merge Sort on Linked Lists! You now have the skills to sort large data sets efficiently, which will serve you well in your programming journey. Keep practicing and exploring new concepts to deepen your understanding and become a proficient developer. Happy coding! 🚀💻