Merge Sort a linked list

What is Merge Sort?

Merge sort is a divide and conquer algorithm that sorts the input list recursively. There are two steps to finish the process:

  • Divide the input list into n sub-list, each sub-list has the same size.
  • Merge the sub-lists into one big list, and each element in the list is ordered.
merge sort process

How to divide a linked list into two parts?

The most intuitive way is to count the total_size of the linked list, then divide the linked list into two parts, each part has the size of total_size / 2. However, we found it takes O(n) time to run because we must iterate the whole linked list in the beginning. The more efficient way is applying two-pointers approaching. Assume we have two pointers: a fast pointer and a slow pointer. In each step, the fast pointer steps across two nodes, the slow pointer only steps across one node. When the fast node approaches the end of the list, the slow pointer is actually standing at the middle point of the linked list. Let’s prove it together:

Assume given list has n nodes, both fast pointer and slow pointer stand at the first node of the list. 
fast pointer: rate is 2 node/step, take n/2 steps to visit all nodes;
slow pointer: rate is 1 node/step, take n steps to visit all nodes.
At the n/2 steps: fast pointer stands at the last node of the list, slow pointer now at n/2 steps * 1 node/step = n/2 node. Is exactly the middle node of the size n linked list.

How to merge two linked lists in ascending order?

Assume we have two sorted linked lists, we want to merge them as a big sorted list. We can have two pointers to indicate the node we’re currently comparing, and append the smaller node into the new node. Let’s see how it works:

l1: 1 -> 3 -> 5
l2: 2 -> 4 -> 6
We start from the first node from the list, i'll mark the current compareing nodes bold. l1: 1 -> 3 -> 5
l2: 2 -> 4 -> 6
reslt: 1 ->
Comparision: 1 < 2, append 1 to the result, move the pointer to its next
l1: 1 -> 3 -> 5
l2: 2 -> 4 -> 6
reslt: 1 -> 2 ->
Comparision: 2 < 3, append 2 to the result, move the pointer to its next
l1: 1 -> 3 -> 5
l2: 2 -> 4 -> 6
reslt: 1 -> 2 -> 3
Comparision: 3 < 4, append 3 to the result, move the pointer to its next
l1: 1 -> 3 -> 5
l2: 2 -> 4 -> 6
reslt: 1 -> 2 -> 3 -> 4
Comparision: 4 < 5, append 4 to the result, move the pointer to its next
l1: 1 -> 3 -> 5
l2: 2 -> 4 -> 6
reslt: 1 -> 2 -> 3 -> 4 -> 5
Comparision: 5 < 6, append 5 to the result, since l1’s pointer meets the end, we simply append all the following nodes after l2’s pointer to the result: 1 -> 2 -> 3 -> 4 -> 5 -> 6

Merge sort a linked list

Now it’s time to build the whole solution with previous key functions. Remember it’s a divide and conquer algorithm, recursion may happen in many places!

class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
#main function
def sortList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head

second = self.break_half(head)
sorted_first = self.sortList(head)
sorted_second = self.sortList(second)

return self.merge(sorted_first, sorted_second)

#will divide the list into two parts evenly, and return the head of the second half
def break_half(self, head):
if not head or not head.next:
return head
slow, fast = head, head.next
while fast and fast.next:
fast = fast.next.next
slow = slow.next

mid = slow.next
slow.next = None

return mid
#merge two list into a big ordered list
def merge(self, l1, l2):
if not l1 and not l2:
return None

if not l1:
return l2

if not l2:
return l1

new_head = None

if l1.val < l2.val:
new_head = l1
new_head.next = self.merge(l1.next, l2)
else:
new_head = l2
new_head.next = self.merge(l1, l2.next)

return new_head

Analyze:

  • Time Complexity: O(nlogn), where n is the number of nodes in the linked list.
  • Space Complexity: O(nlogn), where n is the number of nodes in the linked list. Since the problem is recursive, we need additional space to store the recursive call stack. The maximum depth of the recursion tree is O(nlogn) .

Reference

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store