A method of merging multiple sorted data sets into one sorted set
Most efficient method for linked lists!
- Divide data into minimum unit problems, then sort in order to get final results
top-downapproach
- O(n log n)
- Divide Phase
- Continue dividing the entire data set until it becomes minimum-sized subsets
- Merge Phase
- Sort and merge two subsets into one set
def merge_sort(m):
if len(m) <= 1: # Return immediately if size is 0 or 1
return m
# 1. Divide part
mid = len(m)//2
left = m[:mid]
right = m[mid:]
# Recursively call merge_sort until list size becomes 1
left = merge_sort(left)
right = merge_sort(right)
# 2. Conquer part: Merge divided lists
return merge(left, right)def merge(left, right):
result = [] # Merge two divided lists to create result
while len(left) > 0 and len(right) >0: # When elements remain in both lists
# Compare first elements of two sub lists and add smaller ones to result first
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
if len(left) > 0: # When elements remain in left list
result.extend(left)
if len(right) > 0: # When elements remain in right list
result.extend(right)
return result