subtree(users/wpcarro): docking briefcase at '24f5a642' r/3226

git-subtree-dir: users/wpcarro
git-subtree-mainline: 464bbcb15c09813172c79820bcf526bb10cf4208
git-subtree-split: 24f5a642af3aa1627bbff977f0a101907a02c69f
Change-Id: I6105b3762b79126b3488359c95978cadb3efa789

1 files changed, 28 insertions, 0 deletions

diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/merge-sort.py b/users/wpcarro/scratch/data_structures_and_algorithms/merge-sort.py
new file mode 100644
index 000000000000..6dbe0fa0f3c3
--- /dev/null
+++ b/users/wpcarro/scratch/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]))