Each recusive call divides the unsorted list into halves.
""" Merge sort / Algorithm
Each recusive call divides the unsorted list into halves,
dowm into lists of zero of one lengths.
Then, as the recursive calls return, these smaller lists
are merged toghether into sorted order.
"""defmerge_sort(items, depth=0):if len(items) <= 1: # Base casereturn items
m = len(items) // 2
L = merge_sort(items[:m], depth + 1) # Recursive
R = merge_sort(items[m:], depth + 1)
# At this stage left and right are sorted
print(depth * " ", L, " ", R)
i = 0
j = 0
sorted = []
while len(sorted) < len(items):
# Append the smaller value and # advance tge pointer to next itemif L[i] < R[j]:
sorted.append(L[i])
i = i + 1else:
sorted.append(R[j])
j = j + 1# If one of the pointers has reached the end of its list,# put the rest of the other list into sorted listif i == len(L):
sorted.extend(R[j:])
breakif j == len(R):
sorted.extend(L[i:])
break
print(depth * " ", sorted)
return sorted
data = [2, 9, 8, 5, 3, 4, 7, 6]
print(data)
sorted = merge_sort(data)
print(sorted)
"""
[2, 9, 8, 5, 3, 4, 7, 6]
[2] [9]
[2, 9]
[8] [5]
[5, 8]
[2, 9] [5, 8]
[2, 5, 8, 9]
[3] [4]
[3, 4]
[7] [6]
[6, 7]
[3, 4] [6, 7]
[3, 4, 6, 7]
[2, 5, 8, 9] [3, 4, 6, 7]
[2, 3, 4, 5, 6, 7, 8, 9]
[2, 3, 4, 5, 6, 7, 8, 9]
"""
Timer
Faster then quicksort, almost as fast as native sort().
""" Merge sort algorithm / Speed tests
"""import random
import time
start, end = 0, 0deftimer(func):defwrapper(*args, **kwargs):global start, end
if start == 0:
start = time.time()
result = func(*args, **kwargs)
end = time.time()
return result
return wrapper
@timerdefmerge_sort(items):if len(items) <= 1: # Base casereturn items
m = len(items) // 2
L = merge_sort(items[:m]) # Recursive
R = merge_sort(items[m:])
i = 0
j = 0
sorted = []
while len(sorted) < len(items):
if L[i] < R[j]:
sorted.append(L[i])
i = i + 1else:
sorted.append(R[j])
j = j + 1if i == len(L): sorted.extend(R[j:])
if j == len(R): sorted.extend(L[i:])
return sorted
@timerdefnative_sort(items):return items.sort()
# Time
lst = random.sample(range(0, 300000), 300000)
start, end = 0, 0
sorted = merge_sort(lst)
t1 = end - start
start, end = 0, 0
native_sort(lst)
t2 = end - start
print("merge_sort() 300000 items:", t1, "s")
print("sort() 300000 items:", t2, "s")
"""
merge_sort() 300000 items: 3.0545575618743896 s
sort() 300000 items: 0.10179662704467773 s
"""