# TD 2 - Fusion sort¶

In [49]:
import numpy as np
import random
import time

In [50]:
Tsize = 8
T=np.random.randint(0,100,size=Tsize)
print("Random table T:\n",T,"\n")

Random table T:
[41 23 13 71 68 47 48 24]


Function: mergeSort
INPUT : list T
OUTPUT : recursive dichotomic sorting of T ; calls sort(T)
Function: sort
INPUT : sorted lists T1 and T2
OUTPUT : sorted merged list by iterative scan of both lists
In [25]:
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:])])

In [52]:
mergeSort=trace(mergeSort)

print("\nMergedSorted Array:",mergeSort(T),"\n")

|-- mergeSort([41 23 13 71 68 47 48 24])
|  |-- mergeSort([41 23 13 71 68 47 48 24])
|  |  |-- mergeSort([41 23 13 71 68 47 48 24])
|  |  |  |-- mergeSort([41 23 13 71])
|  |  |  |  |-- mergeSort([41 23 13 71])
|  |  |  |  |  |-- mergeSort([41 23 13 71])
|  |  |  |  |  |  |-- mergeSort([41 23])
|  |  |  |  |  |  |  |-- mergeSort([41 23])
|  |  |  |  |  |  |  |  |-- mergeSort([41 23])
|  |  |  |  |  |  |  |  |  |-- mergeSort([41])
|  |  |  |  |  |  |  |  |  |  |-- mergeSort([41])
|  |  |  |  |  |  |  |  |  |  |  |-- mergeSort([41])
|  |  |  |  |  |  |  |  |  |  |  |  |-- return [41]
|  |  |  |  |  |  |  |  |  |  |  |-- return [41]
|  |  |  |  |  |  |  |  |  |  |-- return [41]
|  |  |  |  |  |  |  |  |  |-- mergeSort([23])
|  |  |  |  |  |  |  |  |  |  |-- mergeSort([23])
|  |  |  |  |  |  |  |  |  |  |  |-- mergeSort([23])
|  |  |  |  |  |  |  |  |  |  |  |  |-- return [23]
|  |  |  |  |  |  |  |  |  |  |  |-- return [23]
|  |  |  |  |  |  |  |  |  |  |-- return [23]
|  |  |  |  |  |  |  |  |  |-- return [23 41]
|  |  |  |  |  |  |  |  |-- return [23 41]
|  |  |  |  |  |  |  |-- return [23 41]
|  |  |  |  |  |  |-- mergeSort([13 71])
|  |  |  |  |  |  |  |-- mergeSort([13 71])
|  |  |  |  |  |  |  |  |-- mergeSort([13 71])
|  |  |  |  |  |  |  |  |  |-- mergeSort([13])
|  |  |  |  |  |  |  |  |  |  |-- mergeSort([13])
|  |  |  |  |  |  |  |  |  |  |  |-- mergeSort([13])
|  |  |  |  |  |  |  |  |  |  |  |  |-- return [13]
|  |  |  |  |  |  |  |  |  |  |  |-- return [13]
|  |  |  |  |  |  |  |  |  |  |-- return [13]
|  |  |  |  |  |  |  |  |  |-- mergeSort([71])
|  |  |  |  |  |  |  |  |  |  |-- mergeSort([71])
|  |  |  |  |  |  |  |  |  |  |  |-- mergeSort([71])
|  |  |  |  |  |  |  |  |  |  |  |  |-- return [71]
|  |  |  |  |  |  |  |  |  |  |  |-- return [71]
|  |  |  |  |  |  |  |  |  |  |-- return [71]
|  |  |  |  |  |  |  |  |  |-- return [13 71]
|  |  |  |  |  |  |  |  |-- return [13 71]
|  |  |  |  |  |  |  |-- return [13 71]
|  |  |  |  |  |  |-- return [13 23 41 71]
|  |  |  |  |  |-- return [13 23 41 71]
|  |  |  |  |-- return [13 23 41 71]
|  |  |  |-- mergeSort([68 47 48 24])
|  |  |  |  |-- mergeSort([68 47 48 24])
|  |  |  |  |  |-- mergeSort([68 47 48 24])
|  |  |  |  |  |  |-- mergeSort([68 47])
|  |  |  |  |  |  |  |-- mergeSort([68 47])
|  |  |  |  |  |  |  |  |-- mergeSort([68 47])
|  |  |  |  |  |  |  |  |  |-- mergeSort([68])
|  |  |  |  |  |  |  |  |  |  |-- mergeSort([68])
|  |  |  |  |  |  |  |  |  |  |  |-- mergeSort([68])
|  |  |  |  |  |  |  |  |  |  |  |  |-- return [68]
|  |  |  |  |  |  |  |  |  |  |  |-- return [68]
|  |  |  |  |  |  |  |  |  |  |-- return [68]
|  |  |  |  |  |  |  |  |  |-- mergeSort([47])
|  |  |  |  |  |  |  |  |  |  |-- mergeSort([47])
|  |  |  |  |  |  |  |  |  |  |  |-- mergeSort([47])
|  |  |  |  |  |  |  |  |  |  |  |  |-- return [47]
|  |  |  |  |  |  |  |  |  |  |  |-- return [47]
|  |  |  |  |  |  |  |  |  |  |-- return [47]
|  |  |  |  |  |  |  |  |  |-- return [47 68]
|  |  |  |  |  |  |  |  |-- return [47 68]
|  |  |  |  |  |  |  |-- return [47 68]
|  |  |  |  |  |  |-- mergeSort([48 24])
|  |  |  |  |  |  |  |-- mergeSort([48 24])
|  |  |  |  |  |  |  |  |-- mergeSort([48 24])
|  |  |  |  |  |  |  |  |  |-- mergeSort([48])
|  |  |  |  |  |  |  |  |  |  |-- mergeSort([48])
|  |  |  |  |  |  |  |  |  |  |  |-- mergeSort([48])
|  |  |  |  |  |  |  |  |  |  |  |  |-- return [48]
|  |  |  |  |  |  |  |  |  |  |  |-- return [48]
|  |  |  |  |  |  |  |  |  |  |-- return [48]
|  |  |  |  |  |  |  |  |  |-- mergeSort([24])
|  |  |  |  |  |  |  |  |  |  |-- mergeSort([24])
|  |  |  |  |  |  |  |  |  |  |  |-- mergeSort([24])
|  |  |  |  |  |  |  |  |  |  |  |  |-- return [24]
|  |  |  |  |  |  |  |  |  |  |  |-- return [24]
|  |  |  |  |  |  |  |  |  |  |-- return [24]
|  |  |  |  |  |  |  |  |  |-- return [24 48]
|  |  |  |  |  |  |  |  |-- return [24 48]
|  |  |  |  |  |  |  |-- return [24 48]
|  |  |  |  |  |  |-- return [24 47 48 68]
|  |  |  |  |  |-- return [24 47 48 68]
|  |  |  |  |-- return [24 47 48 68]
|  |  |  |-- return [13 23 24 41 47 48 68 71]
|  |  |-- return [13 23 24 41 47 48 68 71]
|  |-- return [13 23 24 41 47 48 68 71]

MergedSorted Array: [13 23 24 41 47 48 68 71]



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.

# 2. Iterative version¶

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: iterativeMergeSort
INPUT : list T
OUTPUT : iterative dichotomic sorting of T
In [53]:
def 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

In [55]:
Tsize = 8
T=np.random.randint(0,100,size=Tsize)
print("Random table T:\n",T,"\n")

print("\nIterative sorting of T: ",iterativeMergeSort(T))

Random table T:
[11 48 61  9 97 39 81  2]

range(0, 1) range(1, 2)  -->  range(0, 2)
[11 48 61  9 97 39 81  2]
range(2, 3) range(3, 4)  -->  range(2, 4)
[11 48  9 61 97 39 81  2]
range(4, 5) range(5, 6)  -->  range(4, 6)
[11 48  9 61 39 97 81  2]
range(6, 7) range(7, 8)  -->  range(6, 8)
[11 48  9 61 39 97  2 81]
range(0, 2) range(2, 4)  -->  range(0, 4)
[ 9 11 48 61 39 97  2 81]
range(4, 6) range(6, 8)  -->  range(4, 8)
[ 9 11 48 61  2 39 81 97]
range(0, 4) range(4, 8)  -->  range(0, 8)
[ 2  9 11 39 48 61 81 97]

Iterative sorting of T:  [ 2  9 11 39 48 61 81 97]


# 3. Combination with insertion sort¶

Function: insertionSort
INPUT : list T
OUTPUT : iterative sorting of T by insertion (while going forward in T through i, move index i backwards to its position)
In [69]:
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

In [70]:
Tsize = 8
T=np.random.randint(0,100,size=Tsize)
print("Random table T:\n",T,"\n")

print("\nInsertion sorting of T: ",insertionSort(T))

Random table T:
[85 34 67 81  0 34 19 22]

i = 0

i = 1
|-- j = 0 [85 34 67 81  0 34 19 22]

i = 2
|-- j = 1 [34 85 67 81  0 34 19 22]

i = 3
|-- j = 2 [34 67 85 81  0 34 19 22]

i = 4
|-- j = 3 [34 67 81 85  0 34 19 22]
|-- j = 2 [34 67 81  0 85 34 19 22]
|-- j = 1 [34 67  0 81 85 34 19 22]
|-- j = 0 [34  0 67 81 85 34 19 22]

i = 5
|-- j = 4 [ 0 34 67 81 85 34 19 22]
|-- j = 3 [ 0 34 67 81 34 85 19 22]
|-- j = 2 [ 0 34 67 34 81 85 19 22]

i = 6
|-- j = 5 [ 0 34 34 67 81 85 19 22]
|-- j = 4 [ 0 34 34 67 81 19 85 22]
|-- j = 3 [ 0 34 34 67 19 81 85 22]
|-- j = 2 [ 0 34 34 19 67 81 85 22]
|-- j = 1 [ 0 34 19 34 67 81 85 22]

i = 7
|-- j = 6 [ 0 19 34 34 67 81 85 22]
|-- j = 5 [ 0 19 34 34 67 81 22 85]
|-- j = 4 [ 0 19 34 34 67 22 81 85]
|-- j = 3 [ 0 19 34 34 22 67 81 85]
|-- j = 2 [ 0 19 34 22 34 67 81 85]

Insertion sorting of T:  [ 0 19 22 34 34 67 81 85]


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).$$

## EXTRAS¶

In [5]:
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