# minte9 LearnRemember

### 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: 15 days ago