Skip to content

Instantly share code, notes, and snippets.

@gerep
Created January 26, 2022 12:01
Show Gist options
  • Save gerep/5f1357c9066f5ed4abcc9a912b764591 to your computer and use it in GitHub Desktop.
Save gerep/5f1357c9066f5ed4abcc9a912b764591 to your computer and use it in GitHub Desktop.
import time
import random
def merge_sort(nums):
if len(nums) < 2:
return nums
middle = len(nums) // 2
left = merge_sort(nums[: middle])
right = merge_sort(nums[middle :])
return merge(left, right)
def merge(first, second):
sorted_list = []
i, j = 0, 0
while i < len(first) and j < len(second):
if first[i] < second[j]:
sorted_list.append(first[i])
i += 1
else:
sorted_list.append(second[j])
j += 1
while i < len(first):
sorted_list.append(first[i])
i += 1
while j < len(second):
sorted_list.append(second[j])
j += 1
return sorted_list
# -- TEST SUITE, DONT TOUCH BELOW THIS LINE --
def main():
start = time.time()
o1 = merge_sort(get_nums(10))
o2 = merge_sort(get_nums(100))
merge_sort(get_nums(1000))
merge_sort(get_nums(10000))
end = time.time()
if (end - start) < 2:
print("Fast :)")
else:
print("Slow :(")
print(o1)
print(o2)
def get_nums(num):
nums = []
random.seed(1)
for i in range(num):
nums.append(random.randint(0, len(nums)))
return nums
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment