# Merge Sort¶

In [1]:
%pprint

Pretty printing has been turned OFF

In [2]:
from random import sample
nums = sample(range(1000), k=20)
nums

Out[2]:
[260, 980, 299, 496, 255, 524, 563, 12, 354, 365, 559, 774, 869, 581, 4, 153, 545, 906, 101, 704]
In [9]:
from rcviz import CallGraph, viz

In [12]:
cg = CallGraph()

In [13]:
@viz(cg)
def merge_sort(alist):
print("Splitting ", alist)
if len(alist) > 1:
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]

merge_sort(lefthalf)
merge_sort(righthalf)

i = 0
j = 0
k = 0

while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
alist[k] = lefthalf[i]
i += 1
else:
alist[k] = righthalf[j]
j += 1

while i < len(lefthalf):
alist[k] = lefthalf[i]
i += 1
k+= 1

while j < len(righthalf):
alist[k] = righthalf[j]
j += 1
k += 1

print("Merging ", alist)

In [14]:
merge_sort(nums)

Splitting  [980, 980, 299, 496, 255, 524, 563, 12, 354, 365, 559, 774, 869, 581, 4, 153, 545, 906, 101, 704]
Splitting  [980, 980, 299, 496, 255, 524, 563, 12, 354, 365]
Splitting  [980, 980, 299, 496, 255]
Splitting  [980, 980]
Splitting  [980]
Merging  [980]
Splitting  [980]
Merging  [980]
Merging  [980, 980]
Splitting  [299, 496, 255]
Splitting  [299]
Merging  [299]
Splitting  [496, 255]
Splitting  [496]
Merging  [496]
Splitting  [255]
Merging  [255]
Merging  [496, 255]
Merging  [496, 255, 255]
Merging  [980, 980, 299, 496, 255]
Splitting  [524, 563, 12, 354, 365]
Splitting  [524, 563]
Splitting  [524]
Merging  [524]
Splitting  [563]
Merging  [563]
Merging  [563, 563]
Splitting  [12, 354, 365]
Splitting  [12]
Merging  [12]
Splitting  [354, 365]
Splitting  [354]
Merging  [354]
Splitting  [365]
Merging  [365]
Merging  [365, 365]
Merging  [365, 365, 365]
Merging  [563, 563, 12, 354, 365]
Merging  [980, 980, 299, 496, 255, 524, 563, 12, 354, 365]
Splitting  [559, 774, 869, 581, 4, 153, 545, 906, 101, 704]
Splitting  [559, 774, 869, 581, 4]
Splitting  [559, 774]
Splitting  [559]
Merging  [559]
Splitting  [774]
Merging  [774]
Merging  [774, 774]
Splitting  [869, 581, 4]
Splitting  [869]
Merging  [869]
Splitting  [581, 4]
Splitting  [581]
Merging  [581]
Splitting  [4]
Merging  [4]
Merging  [581, 4]
Merging  [869, 581, 4]
Merging  [869, 581, 4, 581, 4]
Splitting  [153, 545, 906, 101, 704]
Splitting  [153, 545]
Splitting  [153]
Merging  [153]
Splitting  [545]
Merging  [545]
Merging  [545, 545]
Splitting  [906, 101, 704]
Splitting  [906]
Merging  [906]
Splitting  [101, 704]
Splitting  [101]
Merging  [101]
Splitting  [704]
Merging  [704]
Merging  [704, 704]
Merging  [906, 101, 704]
Merging  [906, 101, 704, 101, 704]
Merging  [906, 101, 704, 101, 704, 153, 545, 906, 101, 704]
Merging  [980, 980, 299, 496, 255, 524, 563, 12, 354, 365, 559, 774, 869, 581, 4, 153, 545, 906, 101, 704]

In [15]:
nums

Out[15]:
[980, 980, 299, 496, 255, 524, 563, 12, 354, 365, 559, 774, 869, 581, 4, 153, 545, 906, 101, 704]
In [16]:
cg

callviz: Rendering in inline in Jupyter Notebook

Out[16]: