Revision of mergesort

1 file changed, 44 insertions

mergesort.py(file created)

		@@ -0,0 +1,44 @@
1	+	def merge_sort(array):
2	+	"""split and recursively sort an array"""
3	+
4	+	if len(array) <= 1:
5	+	return array
6	+
7	+	mid = len(array) // 2
8	+	left_slice = array[:mid]
9	+	right_slice = array[mid:]
10	+
11	+	return merge(merge_sort(left_slice), merge_sort(right_slice))
12	+
13	+
14	+	def merge(left, right):
15	+	"""merge 2 sorted arrays"""
16	+	sorted_array = []
17	+	i, j = 0, 0
18	+
19	+	while i < len(left) and j < len(right):
20	+	if left[i] < right[j]:
21	+	sorted_array.append(left[i])
22	+	i += 1
23	+	else:
24	+	sorted_array.append(right[j])
25	+	j += 1
26	+
27	+	# add remaining items, if any
28	+	sorted_array.extend(left[i:])
29	+	sorted_array.extend(right[j:])
30	+	return sorted_array
31	+
32	+
33	+	import random
34	+
35	+
36	+	def generate_random_list(size):
37	+	return random.sample(range(size), size)
38	+
39	+
40	+	a = generate_random_list(1000)
41	+	b = merge_sort(a)
42	+
43	+	print(f"random array : \n{a}")
44	+	print(f"sorted array : \n{b}")

Newer Older