mergesort.py
· 910 B · Python
Raw
def merge_sort(array):
"""split and recursively sort an array"""
if len(array) <= 1:
return array
mid = len(array) // 2
left_slice = array[:mid]
right_slice = array[mid:]
return merge(merge_sort(left_slice), merge_sort(right_slice))
def merge(left, right):
"""merge 2 sorted arrays"""
sorted_array = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
sorted_array.append(left[i])
i += 1
else:
sorted_array.append(right[j])
j += 1
# add remaining items, if any
sorted_array.extend(left[i:])
sorted_array.extend(right[j:])
return sorted_array
import random
def generate_random_list(size):
return random.sample(range(size), size)
a = generate_random_list(1000)
b = merge_sort(a)
print(f"random array : \n{a}")
print(f"sorted array : \n{b}")
| 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}") |