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]:
nodes=39 140548774085280 merge_sort([980, 980, 299, 496, 255, 524, 563, 12, 354, 365, 559, 774, 869, 581, 4, 153, 545, 906, 101, 704]) ret: None 140548774110720 merge_sort([980, 980, 299, 496, 255, 524, 563, 12, 354, 365]) ret: None 140548774085280->140548774110720 1 (⇑19) 140548743540944 merge_sort([906, 101, 704, 101, 704, 153, 545, 906, 101, 704]) ret: None 140548774085280->140548743540944 20 (⇑38) 140548741356688 merge_sort([980, 980, 299, 496, 255]) ret: None 140548774110720->140548741356688 2 (⇑9) 140548743537920 merge_sort([563, 563, 12, 354, 365]) ret: None 140548774110720->140548743537920 11 (⇑18) 140548774128464 merge_sort([980, 980]) ret: None 140548741356688->140548774128464 3 (⇑3) 140548774129520 merge_sort([496, 255, 255]) ret: None 140548741356688->140548774129520 6 (⇑8) 140548774128992 merge_sort([980]) ret: None 140548774128464->140548774128992 4 (⇑1) 140548743522096 merge_sort([980]) ret: None 140548774128464->140548743522096 5 (⇑2) 140548774130048 merge_sort([299]) ret: None 140548774129520->140548774130048 7 (⇑4) 140548770682224 merge_sort([496, 255]) ret: None 140548774129520->140548770682224 8 (⇑7) 140548741361568 merge_sort([496]) ret: None 140548770682224->140548741361568 9 (⇑5) 140548741362096 merge_sort([255]) ret: None 140548770682224->140548741362096 10 (⇑6) 140548770687632 merge_sort([563, 563]) ret: None 140548743537920->140548770687632 12 (⇑12) 140548770688688 merge_sort([365, 365, 365]) ret: None 140548743537920->140548770688688 15 (⇑17) 140548770688160 merge_sort([524]) ret: None 140548770687632->140548770688160 13 (⇑10) 140548774130576 merge_sort([563]) ret: None 140548770687632->140548774130576 14 (⇑11) 140548741371760 merge_sort([12]) ret: None 140548770688688->140548741371760 16 (⇑13) 140548741372288 merge_sort([365, 365]) ret: None 140548770688688->140548741372288 17 (⇑16) 140548743540416 merge_sort([354]) ret: None 140548741372288->140548743540416 18 (⇑14) 140548770689216 merge_sort([365]) ret: None 140548741372288->140548770689216 19 (⇑15) 140548774131104 merge_sort([869, 581, 4, 581, 4]) ret: None 140548743540944->140548774131104 21 (⇑28) 140548743541472 merge_sort([906, 101, 704, 101, 704]) ret: None 140548743540944->140548743541472 30 (⇑37) 140548741371184 merge_sort([774, 774]) ret: None 140548774131104->140548741371184 22 (⇑22) 140548770690272 merge_sort([869, 581, 4]) ret: None 140548774131104->140548770690272 25 (⇑27) 140548774131632 merge_sort([559]) ret: None 140548741371184->140548774131632 23 (⇑20) 140548770689744 merge_sort([774]) ret: None 140548741371184->140548770689744 24 (⇑21) 140548774104448 merge_sort([869]) ret: None 140548770690272->140548774104448 26 (⇑23) 140548774116160 merge_sort([581, 4]) ret: None 140548770690272->140548774116160 27 (⇑26) 140548770690800 merge_sort([581]) ret: None 140548774116160->140548770690800 28 (⇑24) 140548743525056 merge_sort([4]) ret: None 140548774116160->140548743525056 29 (⇑25) 140548774132160 merge_sort([545, 545]) ret: None 140548743541472->140548774132160 31 (⇑31) 140548741365296 merge_sort([906, 101, 704]) ret: None 140548743541472->140548741365296 34 (⇑36) 140548741361024 merge_sort([153]) ret: None 140548774132160->140548741361024 32 (⇑29) 140548774127936 merge_sort([545]) ret: None 140548774132160->140548774127936 33 (⇑30) 140548743525600 merge_sort([906]) ret: None 140548741365296->140548743525600 35 (⇑32) 140548774132688 merge_sort([704, 704]) ret: None 140548741365296->140548774132688 36 (⇑35) 140548770681104 merge_sort([101]) ret: None 140548774132688->140548770681104 37 (⇑33) 140548741374512 merge_sort([704]) ret: None 140548774132688->140548741374512 38 (⇑34)