0%

Merge Sort

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
from copy import deepcopy 

def mergeSort(a1, s, m, t, a):
i = s
j = m + 1
k = s - 1

while (i <= m) and (j <= t):
k += 1
if (a1[i] <= a1[j]):
a[k] = a1[i]
i += 1
else:
a[k] = a1[j]
j += 1

while (i<=m):
k += 1
a[k] = a1[i]
i += 1
while (j<=t):
k += 1
a[k] = a1[j]
j += 1


def mergeSortStep(a, s, t):
a1 = deepcopy(a)
if (s<t):
m = (s+t)//2
mergeSortStep(a1, s, m)
mergeSortStep(a1, m+1, t)
mergeSort(a1, s, m, t, a)

n = int(input('Please input the number of the list: '))
a = list(map(int, input('Please input the unsorted list: ').split()))
mergeSortStep(a, 0, n-1)
for i in range(n):
print(a[i], end=' ')

Hint: shadow/deep copy for lists