Skip to content

Instantly share code, notes, and snippets.

@snoble

snoble/merge.bosatsu

Created December 21, 2019 03:53
Show Gist options
  • Save snoble/db30a967a1ce1a4f80a57549f52f4ddd to your computer and use it in GitHub Desktop.
Save snoble/db30a967a1ce1a4f80a57549f52f4ddd to your computer and use it in GitHub Desktop.
Download ZIP
Merging
Raw
merge.bosatsu
package Merge
def split(sorted, at):
recur sorted:
[]: ([], [])
[h, *rest]:
match cmp_Int(h, at):
GT: ([], sorted)
_:
(left, right) = split(rest, at)
([h, *left], right)
def merge(sorted1, sorted2):
recur sorted1:
[]: sorted2
[head1, *rest1]:
match sorted2:
[]: sorted1
_:
(left, right) = split(sorted2, head1)
[*left, head1, *merge(rest1, right)]
out = merge([1,2,5,6,8],[4,6,7])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment