---
# System prepended metadata

title: ch 2-8
tags: [algorithm, learning, neopolitan]

---

###### 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]
```