Skip to content

Instantly share code, notes, and snippets.

@israelst
Created May 5, 2012 11:21
Show Gist options
  • Save israelst/2601661 to your computer and use it in GitHub Desktop.
Save israelst/2601661 to your computer and use it in GitHub Desktop.
Merging two ordered lists
def merge(x, y):
if len(x) == 0:
return y
if len(y) == 0:
return x
last = y.pop() if x[-1] < y[-1] else x.pop()
# 'merged' is required because the append method is in place
merged = merge(x, y)
merged.append(last)
return merged
def merge(x, y):
if len(x) == 0:
return y
if len(y) == 0:
return x
if x[0] <= y[0]:
return [x[0]] + merge(x[1:], y)
else:
return [y[0]] + merge(x, y[1:])
@juanplopes
Copy link

O problema é que se estamos falando de listas do python, slice e concat custam O(n), o que faz com que seu algoritmo seja O(n^2), que perde todo o sentido.

@israelst
Copy link
Author

israelst commented May 5, 2012

Adicionei uma solução sem slice e concat.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment