-
Notifications
You must be signed in to change notification settings - Fork 41
/
merge_sort.py
64 lines (47 loc) · 1.54 KB
/
merge_sort.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
#__author__ = "Badal"
def merge_sort(array):
"""
This function takes an array and returns a new sorted array.
"""
# find the mid point which takes into account even and odd length arrays
mid = int(len(array) / 2)
if len(array) == 1 :
return array
else:
# recursively call merge_sort on each half of the input array and returns the merged result
return merge(merge_sort(array[:mid]), merge_sort(array[mid:]))
def merge(arr1, arr2):
"""
This function takes two sorted functions and combines them into a new sorted array
"""
max1 = len(arr1)
max2 = len(arr2)
index1 = 0
index2 = 0
result = []
#while loop iterates until either input array has been exhausted
while index1 < max1 and index2 < max2:
if arr1[index1] <= arr2[index2]:
result.append(arr1[index1])
index1 += 1
else:
result.append(arr2[index2])
index2 += 1
# add the array that was not finished to the end of the result array
if index1 == max1:
result += arr2[index2:]
else:
result += arr1[index1:]
return result
test_array = [5, 4, 3, 8, 5, 8, 110, 23123, 32, 55, 4, 34, 4, 6, 53]
print('Please enter a list of numbers with spaces between the numbers.')
print('No need for opening or closing brackets.')
print('Sample input:')
print('5 4 2 33 43 23 9 87 73 72')
user_input = input('Please enter the list of numbers to be sorted: \n')
# convert the string input into an array of strings
user_array = user_input.split()
# convert the strings into floats
for i in range(len(user_array)):
user_array[i] = float(user_array[i])
print(merge_sort(user_array))