###### tags: `learning` `algorithm` `neopolitan`
# ch 2-8
The step-by-step analysis of `mergesort2()`
The sourec code https://github.com/york56/algo_practice/blob/master/ch2_8_debug.py
```
input = [123, 34, 189, 56, 150, 12, 9, 240]
```
```
mergesort2
low = 0 ; high = 7
mid = 3
mergesort2
low = 0 ; high = 3
mid = 1
mergesort2
low = 0 ; high = 1
mid = 0
mergesort2
low = 0 ; high = 0
X
mergesort2
low = 1 ; high = 1
X
merge2
low = 0 ; mid = 0 ; high = 1
i = 0 ; j = 1 ; k = 0
hard-copy U = S[:]
U = [123, 34, 189, 56, 150, 12, 9, 240]
S = [123, 34, 189, 56, 150, 12, 9, 240]
S[ i ] >= S[ j ]
S[ 0 ] >= S[ 1 ]
123 >= 34
U[ k ] is replaced by S[ j ]
U[ 0 ] is replaced by S[ 1 ]
U = [34, 34, 189, 56, 150, 12, 9, 240]
S = [123, 34, 189, 56, 150, 12, 9, 240]
j = 2 > 1 = high
The right is used up
U[k:high+1] is replaced by S[i:mid+1]
U[ 1 : 2 ] is replaced by S[ 0 : 1 ]
[34] [123]
U = [34, 123, 189, 56, 150, 12, 9, 240]
S = [123, 34, 189, 56, 150, 12, 9, 240]
Put U into S
U = [34, 123, 189, 56, 150, 12, 9, 240]
S = [34, 123, 189, 56, 150, 12, 9, 240]
mergesort2
low = 2 ; high = 3
mid = 2
mergesort2
low = 2 ; high = 2
X
mergesort2
low = 3 ; high = 3
X
merge2
low = 2 ; mid = 2 ; high = 3
i = 2 ; j = 3 ; k = 2
hard-copy U = S[:]
U = [34, 123, 189, 56, 150, 12, 9, 240]
S = [34, 123, 189, 56, 150, 12, 9, 240]
S[ i ] >= S[ j ]
S[ 2 ] >= S[ 3 ]
189 >= 56
U[ k ] is replaced by S[ j ]
U[ 2 ] is replaced by S[ 3 ]
U = [34, 123, 56, 56, 150, 12, 9, 240]
S = [34, 123, 189, 56, 150, 12, 9, 240]
j = 4 > 3 = high
The right is used up
U[k:high+1] is replaced by S[i:mid+1]
U[ 3 : 4 ] is replaced by S[ 2 : 3 ]
[56] [189]
U = [34, 123, 56, 189, 150, 12, 9, 240]
S = [34, 123, 189, 56, 150, 12, 9, 240]
Put U into S
U = [34, 123, 56, 189, 150, 12, 9, 240]
S = [34, 123, 56, 189, 150, 12, 9, 240]
merge2
low = 0 ; mid = 1 ; high = 3
i = 0 ; j = 2 ; k = 0
hard-copy U = S[:]
U = [34, 123, 56, 189, 150, 12, 9, 240]
S = [34, 123, 56, 189, 150, 12, 9, 240]
S[ i ] < S[ j ]
S[ 0 ] < S[ 2 ]
34 < 56
U[ k ] is replaced by S[ i ]
U[ 0 ] is replaced by S[ 0 ]
U = [34, 123, 56, 189, 150, 12, 9, 240]
S = [34, 123, 56, 189, 150, 12, 9, 240]
S[ i ] >= S[ j ]
S[ 1 ] >= S[ 2 ]
123 >= 56
U[ k ] is replaced by S[ j ]
U[ 1 ] is replaced by S[ 2 ]
U = [34, 56, 56, 189, 150, 12, 9, 240]
S = [34, 123, 56, 189, 150, 12, 9, 240]
S[ i ] < S[ j ]
S[ 1 ] < S[ 3 ]
123 < 189
U[ k ] is replaced by S[ i ]
U[ 2 ] is replaced by S[ 1 ]
U = [34, 56, 123, 189, 150, 12, 9, 240]
S = [34, 123, 56, 189, 150, 12, 9, 240]
i = 2 > 1 = mid
The left is used up
U[k:high+1] is replaced by S[j:high+1]
U[ 3 : 4 ] is replaced by S[ 3 : 4 ]
[189] [189]
U = [34, 56, 123, 189, 150, 12, 9, 240]
S = [34, 123, 56, 189, 150, 12, 9, 240]
Put U into S
U = [34, 56, 123, 189, 150, 12, 9, 240]
S = [34, 56, 123, 189, 150, 12, 9, 240]
mergesort2
low = 4 ; high = 7
mid = 5
mergesort2
low = 4 ; high = 5
mid = 4
mergesort2
low = 4 ; high = 4
X
mergesort2
low = 5 ; high = 5
X
merge2
low = 4 ; mid = 4 ; high = 5
i = 4 ; j = 5 ; k = 4
hard-copy U = S[:]
U = [34, 56, 123, 189, 150, 12, 9, 240]
S = [34, 56, 123, 189, 150, 12, 9, 240]
S[ i ] >= S[ j ]
S[ 4 ] >= S[ 5 ]
150 >= 12
U[ k ] is replaced by S[ j ]
U[ 4 ] is replaced by S[ 5 ]
U = [34, 56, 123, 189, 12, 12, 9, 240]
S = [34, 56, 123, 189, 150, 12, 9, 240]
j = 6 > 5 = high
The right is used up
U[k:high+1] is replaced by S[i:mid+1]
U[ 5 : 6 ] is replaced by S[ 4 : 5 ]
[12] [150]
U = [34, 56, 123, 189, 12, 150, 9, 240]
S = [34, 56, 123, 189, 150, 12, 9, 240]
Put U into S
U = [34, 56, 123, 189, 12, 150, 9, 240]
S = [34, 56, 123, 189, 12, 150, 9, 240]
mergesort2
low = 6 ; high = 7
mid = 6
mergesort2
low = 6 ; high = 6
X
mergesort2
low = 7 ; high = 7
X
merge2
low = 6 ; mid = 6 ; high = 7
i = 6 ; j = 7 ; k = 6
hard-copy U = S[:]
U = [34, 56, 123, 189, 12, 150, 9, 240]
S = [34, 56, 123, 189, 12, 150, 9, 240]
S[ i ] < S[ j ]
S[ 6 ] < S[ 7 ]
9 < 240
U[ k ] is replaced by S[ i ]
U[ 6 ] is replaced by S[ 6 ]
U = [34, 56, 123, 189, 12, 150, 9, 240]
S = [34, 56, 123, 189, 12, 150, 9, 240]
i = 7 > 6 = mid
The left is used up
U[k:high+1] is replaced by S[j:high+1]
U[ 7 : 8 ] is replaced by S[ 7 : 8 ]
[240] [240]
U = [34, 56, 123, 189, 12, 150, 9, 240]
S = [34, 56, 123, 189, 12, 150, 9, 240]
Put U into S
U = [34, 56, 123, 189, 12, 150, 9, 240]
S = [34, 56, 123, 189, 12, 150, 9, 240]
merge2
low = 4 ; mid = 5 ; high = 7
i = 4 ; j = 6 ; k = 4
hard-copy U = S[:]
U = [34, 56, 123, 189, 12, 150, 9, 240]
S = [34, 56, 123, 189, 12, 150, 9, 240]
S[ i ] >= S[ j ]
S[ 4 ] >= S[ 6 ]
12 >= 9
U[ k ] is replaced by S[ j ]
U[ 4 ] is replaced by S[ 6 ]
U = [34, 56, 123, 189, 9, 150, 9, 240]
S = [34, 56, 123, 189, 12, 150, 9, 240]
S[ i ] < S[ j ]
S[ 4 ] < S[ 7 ]
12 < 240
U[ k ] is replaced by S[ i ]
U[ 5 ] is replaced by S[ 4 ]
U = [34, 56, 123, 189, 9, 12, 9, 240]
S = [34, 56, 123, 189, 12, 150, 9, 240]
S[ i ] < S[ j ]
S[ 5 ] < S[ 7 ]
150 < 240
U[ k ] is replaced by S[ i ]
U[ 6 ] is replaced by S[ 5 ]
U = [34, 56, 123, 189, 9, 12, 150, 240]
S = [34, 56, 123, 189, 12, 150, 9, 240]
i = 6 > 5 = mid
The left is used up
U[k:high+1] is replaced by S[j:high+1]
U[ 7 : 8 ] is replaced by S[ 7 : 8 ]
[240] [240]
U = [34, 56, 123, 189, 9, 12, 150, 240]
S = [34, 56, 123, 189, 12, 150, 9, 240]
Put U into S
U = [34, 56, 123, 189, 9, 12, 150, 240]
S = [34, 56, 123, 189, 9, 12, 150, 240]
merge2
low = 0 ; mid = 3 ; high = 7
i = 0 ; j = 4 ; k = 0
hard-copy U = S[:]
U = [34, 56, 123, 189, 9, 12, 150, 240]
S = [34, 56, 123, 189, 9, 12, 150, 240]
S[ i ] >= S[ j ]
S[ 0 ] >= S[ 4 ]
34 >= 9
U[ k ] is replaced by S[ j ]
U[ 0 ] is replaced by S[ 4 ]
U = [9, 56, 123, 189, 9, 12, 150, 240]
S = [34, 56, 123, 189, 9, 12, 150, 240]
S[ i ] >= S[ j ]
S[ 0 ] >= S[ 5 ]
34 >= 12
U[ k ] is replaced by S[ j ]
U[ 1 ] is replaced by S[ 5 ]
U = [9, 12, 123, 189, 9, 12, 150, 240]
S = [34, 56, 123, 189, 9, 12, 150, 240]
S[ i ] < S[ j ]
S[ 0 ] < S[ 6 ]
34 < 150
U[ k ] is replaced by S[ i ]
U[ 2 ] is replaced by S[ 0 ]
U = [9, 12, 34, 189, 9, 12, 150, 240]
S = [34, 56, 123, 189, 9, 12, 150, 240]
S[ i ] < S[ j ]
S[ 1 ] < S[ 6 ]
56 < 150
U[ k ] is replaced by S[ i ]
U[ 3 ] is replaced by S[ 1 ]
U = [9, 12, 34, 56, 9, 12, 150, 240]
S = [34, 56, 123, 189, 9, 12, 150, 240]
S[ i ] < S[ j ]
S[ 2 ] < S[ 6 ]
123 < 150
U[ k ] is replaced by S[ i ]
U[ 4 ] is replaced by S[ 2 ]
U = [9, 12, 34, 56, 123, 12, 150, 240]
S = [34, 56, 123, 189, 9, 12, 150, 240]
S[ i ] >= S[ j ]
S[ 3 ] >= S[ 6 ]
189 >= 150
U[ k ] is replaced by S[ j ]
U[ 5 ] is replaced by S[ 6 ]
U = [9, 12, 34, 56, 123, 150, 150, 240]
S = [34, 56, 123, 189, 9, 12, 150, 240]
S[ i ] < S[ j ]
S[ 3 ] < S[ 7 ]
189 < 240
U[ k ] is replaced by S[ i ]
U[ 6 ] is replaced by S[ 3 ]
U = [9, 12, 34, 56, 123, 150, 189, 240]
S = [34, 56, 123, 189, 9, 12, 150, 240]
i = 4 > 3 = mid
The left is used up
U[k:high+1] is replaced by S[j:high+1]
U[ 7 : 8 ] is replaced by S[ 7 : 8 ]
[240] [240]
U = [9, 12, 34, 56, 123, 150, 189, 240]
S = [34, 56, 123, 189, 9, 12, 150, 240]
Put U into S
U = [9, 12, 34, 56, 123, 150, 189, 240]
S = [9, 12, 34, 56, 123, 150, 189, 240]
```
```
output = [9, 12, 34, 56, 123, 150, 189, 240]
```
Sign in with Wallet
Connect another wallet