Skip to content

Instantly share code, notes, and snippets.

@matheusportela
Created August 15, 2016 10:57
Show Gist options
  • Save matheusportela/969fbccba1706e06a6238b5e729544c9 to your computer and use it in GitHub Desktop.
Save matheusportela/969fbccba1706e06a6238b5e729544c9 to your computer and use it in GitHub Desktop.
Naive merge sort implementation
def merg(a, b):
# This method takes care of merging two lists while maintaining it sorted.
# Hence, it must only return the resulting merged list, not the indices i
# and j.
c = [None] * int(len(a) + len(b))
i = 0
j = 0
k = 0 # This will take care of where we are placing the new elements
# i and j must be strictly less than the lengths, otherwise they'll overflow
# Example: for len(a) = 10, i = 10 is out-of-bounds since indices go from 0
# to 9.
while i < len(a) and j < len(b):
if a[i] < b[j]:
c[k] = a[i]
i = i+1
# Don't return i
else:
c[k] = b[j]
j = j+1
# Don't return j
k += 1
# It might happen that we placed all elements from "b" but there are still
# some "a" elements left. Let's place them where:
while i < len(a):
c[k] = a[i]
i = i+1
k = k+1
# Same rationale here but placing "b" elements this time
while j < len(b):
c[k] = b[j]
j = j+1
k = k+1
return c
def msort(x):
if len(x) == 1:
return x
else:
lx = int(len(x)/2) # No need to round. int(x) already makes it an integer
A = x[:lx] # Empty left boundary makes the slice start from the beginning
B = x[lx:] # Empty right boundary makes the slice goes until the end
A = msort(A)
B = msort(B)
return merg(A, B)
def main():
import random
random.seed(0)
x = range(10)
random.shuffle(x)
print msort(x)
if __name__ == '__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment