mergesort algorithm misunderstanding

Question

Python student here,

I have been studying up on basic algorithms and I am having some trouble fully understanding MergeSort. I believe I understand the divide and conquer approach, how namespaces are created within each loop cycle, and how the algorithm splits up the elements. Where I get a bit confused is in how it reassembles/merges the elements, successively taking on the sorted values.

I think I understand everything from results line 21 to 37. i.e. how nlist is transformed to [27, 43]. My specific question is regarding results line 38 and how righthalf which was [43, 27] at result line 21, takes on the value of nlist which is [27, 43] (results line 38).

As I do not see any variable assignment of nlist to righthalf,

i.e. righthalf = nlist is not in the code flow between 'results' lines 37 & 38

MergeSort Algorithm (with diagnostic print statements):

def mergeSort(nlist):
    print("Splitting ", nlist)
    if len(nlist) > 1:
        mid = len(nlist) // 2
        lefthalf = nlist[: mid]
        righthalf = nlist[mid :]
        print('wow', 'lefthalf', lefthalf)
        mergeSort(lefthalf)
        print('this is the right1', righthalf)
        mergeSort(righthalf)
        print('this is the right2', righthalf)
        i = j = k = 0

        print("cool")
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                print('bot', 'k', 'i', 'j', 'lefthalf', 'righthalf', k, i, j, lefthalf, righthalf)
                nlist[k] = lefthalf[i]
                print('nlist[k]', nlist[k], nlist)
                i = i + 1
            else:
                print('me')
                nlist[k] = righthalf[j]
                print('k', 'nlist[k]', k, nlist[k], nlist)
                print(righthalf)
                j = j + 1

            k = k + 1

        while i < len(lefthalf):
            print('cot', 'k', 'i', 'lefthalf', k, i, lefthalf)
            nlist[k] = lefthalf[i]
            print('nlist[k]', nlist[k], nlist)
            i = i + 1
            k = k + 1

        while j < len(righthalf):
            print('dot', 'k', 'j', 'righthalf', k, j, righthalf)
            nlist[k] = righthalf[j]
            print('nlist[k]', nlist[k], nlist)
            j = j + 1
            k = k + 1

    print("Merging ", nlist)

nlist = [14, 46, 43, 27, 57, 41, 45, 21, 70]
mergeSort(nlist)
print(nlist) 

Results

1     Splitting  [14, 46, 43, 27, 57, 41, 45, 21, 70]
2     wow lefthalf [14, 46, 43, 27]
3     Splitting  [14, 46, 43, 27]
4     wow lefthalf [14, 46]
5     Splitting  [14, 46]
6     wow lefthalf [14]
7     Splitting  [14]
8     Merging  [14]
9     yah righthalf [46]
10    this is the right1 [46]
11    Splitting  [46]
12    Merging  [46]
13    this is the right2 [46]
14    cool
15    bot k i j lefthalf righthalf 0 0 0 [14] [46]
16    nlist[k] 14 [14, 46]
17    dot k j righthalf 1 0 [46]
18    nlist[k] 46 [14, 46]
19    Merging  [14, 46]
20    yah righthalf [43, 27]
21    this is the right1 [43, 27]
22    Splitting  [43, 27]
23    wow lefthalf [43]
24    Splitting  [43]
25    Merging  [43]
26    yah righthalf [27]
27    this is the right1 [27]
28    Splitting  [27]
29    Merging  [27]
30    this is the right2 [27]
31    cool
32    me
33    k nlist[k] 0 27 [27, 27]
34    [27]
35    cot k i lefthalf 1 0 [43]
36    nlist[k] 43 [27, 43]
37    Merging  [27, 43]
38    this is the right2 [27, 43]
39    cool
40    bot k i j lefthalf righthalf 0 0 0 [14, 46] [27, 43]
41    nlist[k] 14 [14, 46, 43, 27]
42    me
43    k nlist[k] 1 27 [14, 27, 43, 27]
44    [27, 43]
45    me
46    k nlist[k] 2 43 [14, 27, 43, 27]
47    [27, 43]
48    cot k i lefthalf 3 1 [14, 46]
49    nlist[k] 46 [14, 27, 43, 46]
50    Merging  [14, 27, 43, 46]
51    yah righthalf [57, 41, 45, 21, 70]
52    this is the right1 [57, 41, 45, 21, 70]
53    Splitting  [57, 41, 45, 21, 70]
54    wow lefthalf [57, 41]
55    Splitting  [57, 41]
56    wow lefthalf [57]
57    Splitting  [57]
58    Merging  [57]
59    yah righthalf [41]
60    this is the right1 [41]
61    Splitting  [41]
62    Merging  [41]
63    this is the right2 [41]
64    cool
65    me
66    k nlist[k] 0 41 [41, 41]
67    [41]
68    cot k i lefthalf 1 0 [57]
69    nlist[k] 57 [41, 57]
70    Merging  [41, 57]
71    yah righthalf [45, 21, 70]
72    this is the right1 [45, 21, 70]
73    Splitting  [45, 21, 70]
74    wow lefthalf [45]
75    Splitting  [45]
76    Merging  [45]
77    yah righthalf [21, 70]
78    this is the right1 [21, 70]
79    Splitting  [21, 70]
80    wow lefthalf [21]
81    Splitting  [21]
82    Merging  [21]
83    yah righthalf [70]
84    this is the right1 [70]
85    Splitting  [70]
86    Merging  [70]
87    this is the right2 [70]
88    cool
89    bot k i j lefthalf righthalf 0 0 0 [21] [70]
90    nlist[k] 21 [21, 70]
91    dot k j righthalf 1 0 [70]
92    nlist[k] 70 [21, 70]
93    Merging  [21, 70]
94    this is the right2 [21, 70]
95    cool
96    me
97    k nlist[k] 0 21 [21, 21, 70]
98    [21, 70]
99    bot k i j lefthalf righthalf 1 0 1 [45] [21, 70]
100   nlist[k] 45 [21, 45, 70]
101   dot k j righthalf 2 1 [21, 70]
102   nlist[k] 70 [21, 45, 70]
103   Merging  [21, 45, 70]
104   this is the right2 [21, 45, 70]
105   cool
106   me
107   k nlist[k] 0 21 [21, 41, 45, 21, 70]
108   [21, 45, 70]
109   bot k i j lefthalf righthalf 1 0 1 [41, 57] [21, 45, 70]
110   nlist[k] 41 [21, 41, 45, 21, 70]
111   me
112   k nlist[k] 2 45 [21, 41, 45, 21, 70]
113   [21, 45, 70]
114   bot k i j lefthalf righthalf 3 1 2 [41, 57] [21, 45, 70]
115   nlist[k] 57 [21, 41, 45, 57, 70]
116   dot k j righthalf 4 2 [21, 45, 70]
117   nlist[k] 70 [21, 41, 45, 57, 70]
118   Merging  [21, 41, 45, 57, 70]
119   this is the right2 [21, 41, 45, 57, 70]
120   cool
121   bot k i j lefthalf righthalf 0 0 0 [14, 27, 43, 46] [21, 41, 45, 57, 70]
122   nlist[k] 14 [14, 46, 43, 27, 57, 41, 45, 21, 70]
123   me
124   k nlist[k] 1 21 [14, 21, 43, 27, 57, 41, 45, 21, 70]
125   [21, 41, 45, 57, 70]
126   bot k i j lefthalf righthalf 2 1 1 [14, 27, 43, 46] [21, 41, 45, 57, 70]
127   nlist[k] 27 [14, 21, 27, 27, 57, 41, 45, 21, 70]
128   me
129   k nlist[k] 3 41 [14, 21, 27, 41, 57, 41, 45, 21, 70]
130   [21, 41, 45, 57, 70]
131   bot k i j lefthalf righthalf 4 2 2 [14, 27, 43, 46] [21, 41, 45, 57, 70]
132   nlist[k] 43 [14, 21, 27, 41, 43, 41, 45, 21, 70]
133   me
134   k nlist[k] 5 45 [14, 21, 27, 41, 43, 45, 45, 21, 70]
135   [21, 41, 45, 57, 70]
136   bot k i j lefthalf righthalf 6 3 3 [14, 27, 43, 46] [21, 41, 45, 57, 70]
137   nlist[k] 46 [14, 21, 27, 41, 43, 45, 46, 21, 70]
138   dot k j righthalf 7 3 [21, 41, 45, 57, 70]
139   nlist[k] 57 [14, 21, 27, 41, 43, 45, 46, 57, 70]
140   dot k j righthalf 8 4 [21, 41, 45, 57, 70]
141   nlist[k] 70 [14, 21, 27, 41, 43, 45, 46, 57, 70]
142   Merging  [14, 21, 27, 41, 43, 45, 46, 57, 70]
143   [14, 21, 27, 41, 43, 45, 46, 57, 70]

Answer 1

Eureka! After an ungodly number of hours spent on this...i have found it.

When a mutable object(in this case a list) is passed into a function as an argument ('righthalf'), and that argument is recursively mutated ('nlist'), the argument is also mutated and this change is reflected outside the function. This represents the "call by object reference" property of python. https://www.geeksforgeeks.org/is-python-call-by-reference-or-call-by-value/

In this specific situation

• 'righthalf' - [43, 27] was passed into the mergesort function as an argument,
• the recursive function received it as 'nlist'
• 'nlist' was mutated into [27, 43] within a recursive function,
• As both point to the same reference location in memory, 'righthalf' is mutated as well and there is no need for the traditional assignment

    righthalf = nlist

Thanks everyone!

Answer 2

Assume you have two sorted lists in front of you. To obtain the merged list, you take the smallest of the two elements at the head of both lists, and repeat until you exhaust both lists.

[*14, 27, 43, 46]
[ 21, 41, 45, 57, 70]

[ 27, 43, 46]
[*21, 41, 45, 57, 70]

[*27, 43, 46]
[ 41, 45, 57, 70]

[ 43, 46]
[*41, 45, 57, 70]

[*43, 46]
[ 45, 57, 70]

[ 46]
[*45, 57, 70]

[*46]
[ 57, 70]

[]
[*57, 70]

[]
[*70]

[]
[]