Add 'universe/' from commit '8ad51b24dd8719840aac47134835ea25cfe1b0b8'

git-subtree-dir: universe
git-subtree-mainline: 15110e6de9f85537c7847267caa35fa068aea001
git-subtree-split: 8ad51b24dd8719840aac47134835ea25cfe1b0b8

1 files changed, 28 insertions, 0 deletions

diff --git a/universe/data_structures_and_algorithms/merge-sort.py b/universe/data_structures_and_algorithms/merge-sort.py
new file mode 100644
index 000000000000..6dbe0fa0f3c3
--- /dev/null
+++ b/universe/data_structures_and_algorithms/merge-sort.py
@@ -0,0 +1,28 @@
+
+
+
+# merge :: [a] -> [a] -> [a]
+# merge([], []): []
+# merge(xs, []): xs
+# merge([], ys): ys
+# merge(xs@[x|xs'], ys@[y|ys'])
+#   when y =< x: cons(y, merge(xs, ys'))
+#   when x < y:  cons(x, merge(xs', ys))
+def merge(xs, ys):
+    if xs == [] and ys == []:
+        return []
+    elif ys == []:
+        return xs
+    elif xs == []:
+        return ys
+    else:
+        x = xs[0]
+        y = ys[0]
+
+        if y <= x:
+            return [y] + merge(xs, ys[1:])
+        else:
+            return [x] + merge(xs[1:], ys)
+        
+print(merge([3, 4, 6, 10, 11, 15],
+            [1, 5, 8, 12, 14, 19]))