Characteristics
1.
Has two index to track of
2.
If index1 > index2 switch order
•
Worst Case:
•
Average Case:
•
Best Case:
Instruction
1.
Split the unsorted array until it is not splittable
2.
Compare the values of the two sublists from the index 0
3.
Append the smaller value to the new list
4.
If either sublist is done comparing, merge the rest of the values from the leftover sublist
5.
Repeat 2 - 4 until sorted
Instructions for Merge Sort
import sys
from load import load_numbers
# load list of numbers
numbers = load_numbers(sys.argv[i])
def merge_sort(values):
if len(values) <= 1:
return values
middle_index = len(values) // 2
left_values = merge_sort(values[:middle_index])
right_values = merge_sort(values[middle_index:])
sorted_values = []
left_index = 0
right_index = 0
while left_index < len(left_values) and right_index < len(right_values):
if left_values[left_index] < right_values[right_index]:
sorted_values.append(left_values[left_index])
left_index += 1
else:
sorted_values.append(right_values[right_index:]
right_index += 1
sorted_values += left_values[left_index:]
sorted_values += right_values[right_index:]
return sorted_values
Python
복사
Instructions for Linked List Merge Sort
from linked_list import LinkedList
# O(kn log n)
def merge_sort(linked_list):
if linked_list.size() == 1:
return linked_list
elif linked_list.heqad 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)
# O(k log n)
def split(linked_list):
# split on a single node #
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
# have to get one node before the mid node to remove next_node connection
mid_node = linked_list.searchByIndex(mid - 1)
left_half = linkded_list
right_half = LinksedList()
# add mid_node + 1 to the newly created right_half
right_half.head = mid_node.next_node
# remove right_half from the left_half
mid_node.next_node = None
return left_half, right_half
# O(n)
def merge(left, right):
merged_list = LinkedList()
# add fake head
merged.add(0)
current_node = merged.head
left_head = left.head
right_head = right_head
while left_head or right_head:
if left_head is None:
current_node.next_node = right_head
right_head = right_head.next_node
elif right_head is None:
current_node.next_node = left.head
left_head. left_head.next_node
else:
left_data = left_head.data
right_data = right_head.data
if left_data < right_data:
current_node.next_node = left_head
else:
current_node.next_node = right_hxffbead
right_head = right_head.next_node
current_node = current_node.next_node
# remove fake head
head = merged_list.head.next_node
merged.head = head
return merged_list
Python
복사
Split Recursively
Sort Recursively
Merge
When Merge
1. left is empty
2. right is empty
3. have to compare
Execute Code
l = LinkedList()
l.add(10)
l.add(2)
l.add(44)
l.add(15)
l.add(200)
print(l)
sorted_linked_list = merge_sort(l)
print(sorted_linked_list)
>>> [Head: 200]→ [15]→ [44]→ [2]→ [Tail: 10]
>>> [Head: 2]→ [10]→ [15]→ [44]→ [Tail: 200]
