diff options
author | William Carroll <wpcarro@gmail.com> | 2020-01-29T14·29+0000 |
---|---|---|
committer | William Carroll <wpcarro@gmail.com> | 2020-01-29T14·29+0000 |
commit | fb9380ba268b3cd27372acadb87b14cc96163374 (patch) | |
tree | f65d7fc8d8726499165a0949af39afd1abc8118c /universe/data_structures_and_algorithms/merge-sort.py | |
parent | 15110e6de9f85537c7847267caa35fa068aea001 (diff) | |
parent | 8ad51b24dd8719840aac47134835ea25cfe1b0b8 (diff) |
Add 'universe/' from commit '8ad51b24dd8719840aac47134835ea25cfe1b0b8'
git-subtree-dir: universe git-subtree-mainline: 15110e6de9f85537c7847267caa35fa068aea001 git-subtree-split: 8ad51b24dd8719840aac47134835ea25cfe1b0b8
Diffstat (limited to 'universe/data_structures_and_algorithms/merge-sort.py')
-rw-r--r-- | universe/data_structures_and_algorithms/merge-sort.py | 28 |
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])) |