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]