import numpy as np
import random
import time
Tsize = 8
T=np.random.randint(0,100,size=Tsize)
print("Random table T:\n",T,"\n")
def mergeSort(T):
if len(T) == 1:
return T
else:
center = len(T) // 2
left = mergeSort(T[:center])
right = mergeSort(T[center:])
return sort(left,right)
def sort(T1,T2):
if len(T1)==0:
return T2
if len(T2)==0:
return T1
if T1[0]<T2[0]:
return np.concatenate([[T1[0]],sort(T1[1:],T2)])
else:
return np.concatenate([[T2[0]],sort(T1,T2[1:])])
mergeSort=trace(mergeSort)
print("\nMergedSorted Array:",mergeSort(T),"\n")
For a table of size $n$, the tree of the trace goes down $\log n+1$ steps and "backs up" $\log n$ steps, hence a total tree depth $$2\log n+1$$
The fusion operations occur when going back up in the tree.
Summing on every level of the tree gives a cost of $n$ every time (because the $n$ entries are spread out on every depth level of the tree). The total complexity is then of order $$ O(n \log n) $$
In memory terms, there is no replacement "in place", so that $2n$ is required to store input and output.
This version is not easy to implement without pen and paper! The table is divided in blocks of two terms which are sorted, and then merged in blocks of four terms, then eight, etc. The implementation keeps track of the number of "intervals" of blocks, the number of which decreases as merging occurs.
Function: iterativeMergeSortdef iterativeMergeSort(T):
intervals = [(j,j+1) for j in range(len(T))] # sliding window of intervals
while len(intervals)>1:
i=0
while i<len(intervals)-1:
I1=intervals[i]
I2=intervals[i+1]
print(range(I1[0],I1[1]),range(I2[0],I2[1])," --> ",range(I1[0],I2[1]))
T[I1[0]:I2[1]]=sort(T[I1[0]:I1[1]],T[I2[0]:I2[1]])
print(T)
intervals[i:i+2]=[(I1[0],I2[1])] # fusing intervals just processed
i+=1
return T
Tsize = 8
T=np.random.randint(0,100,size=Tsize)
print("Random table T:\n",T,"\n")
print("\nIterative sorting of T: ",iterativeMergeSort(T))
def insertionSort(T):
for i,t in enumerate(T):
j = i-1
print("\ni =",i)
while j>=0 and T[j]>t:
print("|-- j =",j,T)
T[j+1],T[j] = T[j],t
j-=1
return T
Tsize = 8
T=np.random.randint(0,100,size=Tsize)
print("Random table T:\n",T,"\n")
print("\nInsertion sorting of T: ",insertionSort(T))
In the worst case, a table of size $k$ has a complexity of $\sum_{i=1}^k i\sim O(k^2)$ to be sorted by insertion (that's when it is sorted in a reversed manner). So, after $i=\log (n/k)$ steps of dichotomy by mergeSort of a table of size $n$, the cumulative cost of insertionSort is $$O(k^2(n/k))=O(kn).$$
The additional cost of the $i=\log (n/k)$ mergeSort operations is $O(n\log (n/k))$, leading up to a final total cost of: $$ O(nk + n\log (n/k)).$$
The best choice for $k$ is when the two complexities in the sum are of the same order, so $k\sim \log(n/k)=\log n - \log k$, which in the first order is $$ k \sim \log n$$ and the resulting total cost is $$ O(n\log n). $$
from functools import wraps
def trace(func):
func_name = func.__name__
separator = '| '
trace.recursion_depth = 0
@wraps(func)
def traced_func(*args, **kwargs):
# repeat separator N times (where N is recursion depth)
# `map(str, args)` prepares the iterable with str representation of positional arguments
# `", ".join(map(str, args))` will generate comma-separated list of positional arguments
# `"x"*5` will print `"xxxxx"` - so we can use multiplication operator to repeat separator
print(f'{separator * trace.recursion_depth}|-- {func_name}({", ".join(map(str, args))})')
# we're diving in
trace.recursion_depth += 1
result = func(*args, **kwargs)
# going out of that level of recursion
trace.recursion_depth -= 1
# result is printed on the next level
print(f'{separator * (trace.recursion_depth + 1)}|-- return {result}')
return result
return traced_func