"""
PROJECT 3 - Merge Sort
Name:
PID:
"""
from Project3.LinkedList import LinkedList
def merge_lists(lists, threshold):
"""
Time Complexity: O(mnlgn)
n: Linked List size
m: Amount of Linked Lists
Space Complexity: O(nm)
:param lists: a list of n different unsorted LinkedLists
:param threshold: use insertion sort when the Linkedlist
is smaller than or equal to the threshold
:return: the final sorted and comined linkedlist
"""
pass
def merge_sort(linked_list, threshold):
"""
Time Complexity: θ(nlgn)
Space Complexity: O(n)
must be recursive
:param linked_list: an unsorted singly linkedlist
:param threshold: use insertion sort when the linked list
is smaller than or equal to the threshold
:return: the sorted linked list
"""
pass
def split_linked_list(linked_list):
"""
Time Complexity: O(n)
Space Complexity: O(n)
This function will take a linked list and split it in half.
If the size is odd, split it into sizes (n/2, n/2 +1)
:param linked_list: the provided linked list
:return: a tuple of 2 linked lists
"""
pass
def merge(list1, list2):
"""
Time Complexity: θ(n+m)
n: size of first list
m: size of second list
Space Complexity: O(n+m)
This function takes in 2 sorted
LinkedLists and merges them together.
:param list1: the first half of the linked list
:param list2: the second half of the linked list
:return: one sorted linked list
"""
pass