Skip to content

Instantly share code, notes, and snippets.

@jamescasia
Created March 12, 2022 16:10
Show Gist options
  • Save jamescasia/354e1b8e9577db9b9044e85ebdb4f9c1 to your computer and use it in GitHub Desktop.
Save jamescasia/354e1b8e9577db9b9044e85ebdb4f9c1 to your computer and use it in GitHub Desktop.
Merge sort algorithm
def mergesort(array):
left = array[:len(array)//2]
right = array[len(array)//2:]
left = mergesort(left) if len(left) >= 2 else left
right = mergesort(right) if len(right) >= 2 else right
res = []
l = 0
r = 0
while l < len(left) or r < len(right):
if l == len(left):
res.append(right[r])
r += 1
elif r == len(right):
res.append(left[l])
l += 1
elif left[l] < right[r]:
res.append(left[l])
l += 1
else:
res.append(right[r])
r += 1
return res
print(mergesort([2, 8, 5, 3, 9, 4, 1, 7]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment