Skip to content

Instantly share code, notes, and snippets.

@antunesleo
Created April 25, 2020 14:39
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save antunesleo/ae86bea349c44f896f4c54a3075d9ba1 to your computer and use it in GitHub Desktop.
Save antunesleo/ae86bea349c44f896f4c54a3075d9ba1 to your computer and use it in GitHub Desktop.
Merge sort in python
def merge_sort(ar, start, end):
qtd = end - start
if qtd > 1:
mid = int((start + end) / 2)
merge_sort(ar, start, mid)
merge_sort(ar, mid, end)
intercalate(ar, start, mid, end)
return ar
def intercalate(ar, start, mid, end):
sorted_ar = []
i = start
j = mid
while i < mid and j < end:
if ar[i] < ar[j]:
sorted_ar.append(ar[i])
i += 1
else:
sorted_ar.append(ar[j])
j += 1
while i < mid:
sorted_ar.append(ar[i])
i += 1
while j < end:
sorted_ar.append(ar[j])
j += 1
for i in range(0, len(sorted_ar)):
ar[start + i] = sorted_ar[i]
merge_sort([99, 206, -77, 2, 3, 6, 1, 4, 5, 8, 25], 0, 11)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment