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

Takes O(n log n) time
Takes O(n) space
"""

left = merge_sort(left_half)
right = merge_sort(right_half)

return merge(left, right)

"""
Divide the unsorted list at midpoint into sublists
Takes O(log n) time
"""
right_half = None

return left_half, right_half
else:
mid = size//2

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

# Iterate over left and right as long until the tail node of both
# left and right
# If the head node of left is None, we're at the tail
# Add the tail node from right to the merged linked list
# Call next on right to set loop condition to False
# If the head node of right is None, we're at the tail
# Add the tail node from left to the merged linked list
# Call next on left to set loop condition to False
else:
# Not at either tail node
# Obtain node data to perform comparison operations

# If data on left is lesser than right set current to left node
# Move left head to next node
if left_data < right_data:
# If data on left is greater than right set current to right node
# Move right head to next node
else: