forked from kiat/Elements-of-Software-Design
-
Notifications
You must be signed in to change notification settings - Fork 0
/
example_006_mergesort.py
73 lines (55 loc) · 1.83 KB
/
example_006_mergesort.py
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
69
70
71
72
73
'''Example of merge sort implementation.'''
def merge(arr, left_i, mid_i, right_i):
'''
Merge Procedure function of two sorted arrays. Here the two arrays are
within the same are on the left and right side. The left side index is from
[left to mid] and right side is from [mid to right]
'''
n_1 = mid_i - left_i + 1
n_2 = right_i - mid_i
# allocate temp lists with sizes of n1 and n2
left = [0] * n_1
right = [0] * n_2
# We copy the data to temp lists of left and right
for i in range(0, n_1):
left[i] = arr[left_i + i]
for j in range(0, n_2):
right[j] = arr[mid_i + 1 + j]
# Merge the temp lists back into orginal
# Initialization
i = 0 # Initial index of first subarray
j = 0 # Initial index of second subarray
k = left_i # Initial index of merged subarray
while i < n_1 and j < n_2:
if left[i] <= right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1
# Copy the remaining elements of left[]
while i < n_1:
arr[k] = left[i]
i += 1
k += 1
# Copy the remaining elements of right[]
while j < n_2:
arr[k] = right[j]
j += 1
k += 1
def merge_sort(arr, left, right):
'''Merge sort algorithm'''
if left < right:
# Same as (l+r)//2, but avoids overflow for
# large l and h
mid = left + (right - left) // 2
# Sort first and second halves
merge_sort(arr, left, mid) # recursive call
merge_sort(arr, mid+1, right) # recursive call
merge(arr, left, mid, right) # merge them
# Let us test it
my_arr = [9, 12, 18, 5, 6, 7]
print("Given array is:", my_arr)
merge_sort(my_arr, 0, len(my_arr)-1)
print("Sorted array is: ", my_arr)