Skip to content

Instantly share code, notes, and snippets.

@ugovaretto
Created January 28, 2016 13:32
Show Gist options
  • Save ugovaretto/bf9a161155047520143c to your computer and use it in GitHub Desktop.
Save ugovaretto/bf9a161155047520143c to your computer and use it in GitHub Desktop.
merge sorted lists
#merge sorted lists
def merge(l1, l2):
i1, i2, i = 0, 0, 0
N1, N2 = len(l1), len(l2)
N = N1 + N2
l = []
for i in range(N):
if i1 == N1:
l.extend(l2[i2:])
break
if i2 == N2:
l.extend(l1[i1:])
break
if l1[i1] < l2[i2]:
l.append(l1[i1])
i1 += 1
else:
l.append(l2[i2])
i2 += 1
return l
assert merge([1, 10, 100, 1000], [0, 2, 3, 200]) == [0, 1, 2, 3, 10, 100, 200, 1000]
assert merge([1, 10, 100, 1000], [0, 2, 200]) == [0, 1, 2, 10, 100, 200, 1000]
assert merge([1, 10, 100], [0, 2, 3, 200]) == [0, 1, 2, 3, 10, 100, 200]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment