Add mergesort

hanss314 · abranhe · commit f7f877bff8cc · 2018-10-02T15:00:34.000-04:00
diff --git a/sorting/merge_sort.py b/sorting/merge_sort.py
@@ -0,0 +1,20 @@
+def merge_sort(l):
+    if len(l) < 2: return
+    pivot = len(l)//2
+    left, right = l[:pivot], l[pivot:]
+    merge_sort(left)
+    merge_sort(right)
+
+    k = 0
+    while len(left) > 0 and len(right) > 0:
+        if left[0] < right[0]:
+            l[k] = left.pop(0)
+        else:
+            l[k] = right.pop(0)
+        k += 1
+
+    rest = left + right
+    while len(rest) > 0:
+        l[k] = rest.pop(0)
+        k += 1
+
