Merge Sort
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.
"""
def merge_sort(items, depth=0):
if len(items) <= 1: # Base case
return 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 item
if L[i] < R[j]:
sorted.append(L[i])
i = i + 1
else:
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 list
if i == len(L):
sorted.extend(R[j:])
break
if 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, 0
def timer(func):
def wrapper(*args, **kwargs):
global start, end
if start == 0:
start = time.time()
result = func(*args, **kwargs)
end = time.time()
return result
return wrapper
@timer
def merge_sort(items):
if len(items) <= 1: # Base case
return 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 + 1
else:
sorted.append(R[j])
j = j + 1
if i == len(L): sorted.extend(R[j:])
if j == len(R): sorted.extend(L[i:])
return sorted
@timer
def quicksort(items, i=0, j=None):
if j == None:
j = len(items) - 1
if i > j:
return # Base case
pivot = items[j]
for k in range(i, j + 1):
if items[k] < pivot:
items[i], items[k] = items[k], items[i] # swap items
i = i + 1 # move pointer
if items[k] == pivot:
items[i], items[k] = items[k], items[i] # move pivot
quicksort(items, 0, i - 1) # sort left partition
quicksort(items, i + 1, j) # sort right partition
@timer
def native_sort(items):
return items.sort()
# Time
lst = random.sample(range(0, 300000), 300000)
start, end = 0, 0
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
"""
Last update: 543 days ago
