Skip to content

Instantly share code, notes, and snippets.

@shrkw
Created September 4, 2019 23:23
Show Gist options
  • Save shrkw/0fd48002d2eb0627d118d66a3d312d59 to your computer and use it in GitHub Desktop.
Save shrkw/0fd48002d2eb0627d118d66a3d312d59 to your computer and use it in GitHub Desktop.
merge_sort
from typing import List
import sys
def merge(src1: List, src2: List) -> List:
a = src1[0]
b = src2[0]
res = list()
while len(src1) != 0 or len(src2) != 0:
if a <= b:
res.append(src1.pop(0))
if len(src1) == 0:
a = sys.maxsize
else:
a = src1[0]
else:
res.append(src2.pop(0))
if len(src2) == 0:
b = sys.maxsize
else:
b = src2[0]
print(f"merged: {res}")
return res
def merge_sort(src: List) -> List:
print(f"befre {src}")
if len(src) <= 1:
return src
i = int(len(src) / 2)
return merge(merge_sort(src[:i]), merge_sort(src[i:]))
if __name__ == "__main__":
import random
src = random.sample(range(3000), k=100)
dest = merge_sort(src)
print(dest)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment