Repository navigation
Expand file tree
/
Copy pathMergeSort.py
More file actions
68 lines (65 loc) · 2.56 KB
/
Copy pathMergeSort.py
File metadata and controls
68 lines (65 loc) · 2.56 KB
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
def MergeSort(arr):
res_arr = []
left_index = right_index = 0
if len(arr) <= 1:
return arr
mid = len(arr) // 2
QuickSort(arr, 0, mid)
QuickSort(arr, mid + 1, len(arr) - 1)
left_long = len(arr[0:mid + 1])
right_long = len(arr[mid: len(arr) - 1])
#for i in range(left_long + right_long - 1):# было без -1
while left_index < left_long and right_index + left_long <= len(arr) - 1:
if arr[left_index] < arr[right_index + left_long]:
res_arr.append(arr[left_index])
left_index += 1
if len(res_arr) == len(arr):
return res_arr
if arr[left_index] >= arr[right_index + left_long]:
res_arr.append(arr[right_index + left_long])
right_index += 1
if len(res_arr) == len(arr):
return res_arr
while left_index == left_long:
res_arr.append(arr[right_index + left_long])
right_index += 1
if right_index + left_long > len(arr) - 1:
return res_arr
while right_index + left_long == len(arr):# было len(arr) - 1
res_arr.append(arr[left_index])
left_index += 1
if len(res_arr) == len(arr):
return res_arr
return res_arr
def QuickSort(m, i1, i2):
if i1 == i2:
return m
else:
left = i1
right = i2
if (left + right + 1) // 2 > len(m) - 1:
return
n = m[(left + right + 1) // 2]
ind_supp = (left + right + 1) // 2
while i1 <= i2:
while m[i1] < n:
i1 += 1
while m[i2] > n:
i2 -= 1
if i1 == i2 - 1 and m[i1] > m[i2]:
m[i1], m[i2] = m[i2], m[i1] # меняем местами элементы списка A[i], A[j] = A[j], A[i]
n = m[(left + right + 1) // 2]
ind_supp = (left + right + 1) // 2
i1 = left
i2 = right
continue
if i1 == i2 or i1 == i2 - 1 and m[i1] < m[i2]:
QuickSort(m, left, ind_supp - 1)
return QuickSort(m, ind_supp + 1, right)
if m[i1] >= n and m[i2] <= n:
if m[i1] == n:
ind_supp = i2
if m[i2] == n:
ind_supp = i1
m[i1], m[i2] = m[i2], m[i1] # меняем местами элементы списка A[i], A[j] = A[j], A[i]
return m