Why the merge sort?

If you're not a CS graduate like me and have been grinding endless LeetCode problems and studying DSA, you've probably found yourself wondering: Is there any real meaning to all this?
That moment hit me when I was staring at the merge sort algorithm. I had a very valid question: Why use merge sort when its close cousin quicksort offers the same comforting time complexity of O(n log n)?

That was until I met a different kind of beast: the Linked List.
I like to describe a linked list as a prerequisite to trees—kind of like a one-child tree.

And here's where merge sort truly shines: when you're dealing with linked lists instead of arrays.
Merge sort’s divide-and-conquer philosophy involves splitting the structure (be it a list or linked list) into halves until there’s only one element left, and then merging them back together by comparing elements—essentially deciding “who's the parent of whom.”

<photo credits: Lucas Films>

Here’s a fun example of where merge sort really makes sense with linked lists.
To give a bit of context—when dividing a linked list, you need to find its middle point. Unlike arrays, you can't just index your way to the middle. So, we use a neat little trick called the fast and slow pointer technique. The idea is simple: the fast pointer moves two steps at a time while the slow pointer moves one. By the time the fast pointer reaches the end, the slow one is sitting right in the middle.

You'll actually see this fast-slow pointer trick used in many other algorithms too—especially for detecting cycles. But in this case, it's all about finding the midpoint to split the list for merge sort.

Below is the code for the leet code problem attached. https://leetcode.com/problems/sort-list/

I hope this helps. 

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, val=0, next=None):

#         self.val = val

#         self.next = next

class Solution:

    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:

        if not head or not head.next:

            return head

        

        #split the list in two half

        left = head

        right = self.getMid(head)

        tmp = right.next

        right.next = None

        right = tmp

        left = self.sortList(left)

        right = self.sortList(right)

    

        return self.merge(left, right)

    

    def getMid(self, head): #slow and fast pointer, gives middle of linked list

        slow, fast =head, head.next

        while fast and fast.next:

            slow = slow.next

            fast = fast.next.next

        return slow

    

    def merge(self, list1, list2):

        tail = dummy = ListNode()

        while list1 and list2:

            if list1.val < list2.val:

                tail.next = list1

                list1 = list1.next

            else:

                tail.next = list2

                list2 = list2.next

            tail = tail.next

        

        if list1:

            tail.next = list1

        if list2:

            tail.next = list2

        

        return dummy.next