Skip to content

Instantly share code, notes, and snippets.

@gsinclair
Created March 30, 2020 06:34
Show Gist options
  • Save gsinclair/6f40da414d500bb2c575317f7702d95f to your computer and use it in GitHub Desktop.
Save gsinclair/6f40da414d500bb2c575317f7702d95f to your computer and use it in GitHub Desktop.
Given two sorted lists, return a merged sorted list
# Given two sorted lists A and B, return a sorted list that has all
# the elements of A and all the elements of B.
def merge(A, B):
i, j = 0, 0
result = []
while True:
if i == len(A):
# Put the rest of B into result.
while j < len(B):
result.append(B[j])
j += 1
break
elif j == len(B):
# Put the rest of A into result.
while i < len(A):
result.append(A[i])
i += 1
break
elif A[i] <= B[j]:
# Put the A element into result and increase i.
result.append(A[i])
i += 1
else:
# Put the B element into result and increase j.
result.append(B[j])
j += 1
# We're out of the loop now, so we can return the result.
return result
assert merge([], []) == []
assert merge([4], []) == [4]
assert merge([], [4]) == [4]
assert merge([3], [7]) == [3,7]
assert merge([7], [3]) == [3,7]
A = [3,5,6,9]
B = [1,2,5,7,9]
assert merge(A,B) == [1,2,3,5,5,6,7,9,9]
print("All tests passed.")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment