"ASP.NET MVC Forms" was retired on July 14, 2025.
Well done!
You have completed Introduction to Data Structures!
You have completed Introduction to Data Structures!
Instruction
Implementing Merge Sort on Linked Lists
Python
def merge_sort(linked_list):
"""
Sorts a linked list in ascending order
- Recursively divide the linked list into sublists containing a single node
- Repeatedly merge the sublists to produce sorted sublists until one remains
Returns a sorted linked list
Takes O(n log n) time
Takes O(n) space
"""
if linked_list.size() == 1:
return linked_list
elif linked_list.head is None:
return linked_list
left_half, right_half = split(linked_list)
left = merge_sort(left_half)
right = merge_sort(right_half)
return merge(left, right)
def split(linked_list):
"""
Divide the unsorted list at midpoint into sublists
Takes O(log n) time
"""
if linked_list == None or linked_list.head == None:
left_half = linked_list
right_half = None
return left_half, right_half
else:
size = linked_list.size()
mid = size//2
mid_node = linked_list.node_at_index(mid-1)
left_half = linked_list
right_half = LinkedList()
right_half.head = mid_node.next_node
mid_node.next_node = None
return left_half, right_half
def merge(left, right):
"""
Merges two linked lists, sorting by data in nodes
Returns a new merged list
Takes O(n) space
Runs in O(n) time
"""
# Create a new linked list that contains nodes from merging left and right
merged = LinkedList()
# Add a fake head that is discarded later.
merged.add(0)
# Set current to the head of the linked list
current = merged.head
# Obtain head nodes for left and right linked lists
left_head = left.head
right_head = right.head
# Iterate over left and right as long until the tail node of both
# left and right
while left_head or right_head:
# If the head node of left is None, we're at the tail
# Add the tail node from right to the merged linked list
if left_head is None:
current.next_node = right_head
# Call next on right to set loop condition to False
right_head = right_head.next_node
# If the head node of right is None, we're at the tail
# Add the tail node from left to the merged linked list
elif right_head is None:
current.next_node = left_head
# Call next on left to set loop condition to False
left_head = left_head.next_node
else:
# Not at either tail node
# Obtain node data to perform comparison operations
left_data = left_head.data
right_data = right_head.data
# If data on left is lesser than right set current to left node
# Move left head to next node
if left_data < right_data:
current.next_node = left_head
left_head = left_head.next_node
# If data on left is greater than right set current to right node
# Move right head to next node
else:
current.next_node = right_head
right_head = right_head.next_node
# Move current to next node
current = current.next_node
# Discard fake head and set first merged node as head
head = merged.head.next_node
merged.head = head
return merged