Skip to content

Instantly share code, notes, and snippets.

@dhruvbird
Forked from antani/gist:144a2dfc85d89ae86297
Last active August 29, 2015 14:07
Show Gist options
  • Save dhruvbird/9b520fa767655c56e3fe to your computer and use it in GitHub Desktop.
Save dhruvbird/9b520fa767655c56e3fe to your computer and use it in GitHub Desktop.
def merge_sort(msg, m, depth=0):
print " " * depth, msg, m
result=[]
#Exit condition
if len(m) < 2:
return m
mid = int(len(m)/2)
left = m[:mid]
right = m[mid:]
#print "left:",left," : right :", right
left = merge_sort("Calling for left (caller: {0})".format(m), left, depth+1)
right = merge_sort("Calling for right (caller: {0})".format(m), right, depth+1)
#Merge now
i = 0
j = 0
while i < len(left) and j < len(right):
print " LOOP - left:",left," : right :", right
if left[i] > right[j]:
result.append(right[j])
j += 1
else:
result.append(left[i])
i += 1
print "result: ",result
result += left[i:]
result += right[j:]
print " result: ",result
return result
if __name__ == "__main__":
print merge_sort("Main",[9,8,7,6,5,4,3,2,1])
------------------------------------------------------------------------------------------------------------
Results in the following output:
Main [9, 8, 7, 6, 5, 4, 3, 2, 1]
Calling for left (caller: [9, 8, 7, 6, 5, 4, 3, 2, 1]) [9, 8, 7, 6]
Calling for left (caller: [9, 8, 7, 6]) [9, 8]
Calling for left (caller: [9, 8]) [9]
Calling for right (caller: [9, 8]) [8]
LOOP - left: [9] : right : [8]
result: [8]
result: [8, 9]
Calling for right (caller: [9, 8, 7, 6]) [7, 6]
Calling for left (caller: [7, 6]) [7]
Calling for right (caller: [7, 6]) [6]
LOOP - left: [7] : right : [6]
result: [6]
result: [6, 7]
LOOP - left: [8, 9] : right : [6, 7]
result: [6]
LOOP - left: [8, 9] : right : [6, 7]
result: [6, 7]
result: [6, 7, 8, 9]
Calling for right (caller: [9, 8, 7, 6, 5, 4, 3, 2, 1]) [5, 4, 3, 2, 1]
Calling for left (caller: [5, 4, 3, 2, 1]) [5, 4]
Calling for left (caller: [5, 4]) [5]
Calling for right (caller: [5, 4]) [4]
LOOP - left: [5] : right : [4]
result: [4]
result: [4, 5]
Calling for right (caller: [5, 4, 3, 2, 1]) [3, 2, 1]
Calling for left (caller: [3, 2, 1]) [3]
Calling for right (caller: [3, 2, 1]) [2, 1]
Calling for left (caller: [2, 1]) [2]
Calling for right (caller: [2, 1]) [1]
LOOP - left: [2] : right : [1]
result: [1]
result: [1, 2]
LOOP - left: [3] : right : [1, 2]
result: [1]
LOOP - left: [3] : right : [1, 2]
result: [1, 2]
result: [1, 2, 3]
LOOP - left: [4, 5] : right : [1, 2, 3]
result: [1]
LOOP - left: [4, 5] : right : [1, 2, 3]
result: [1, 2]
LOOP - left: [4, 5] : right : [1, 2, 3]
result: [1, 2, 3]
result: [1, 2, 3, 4, 5]
LOOP - left: [6, 7, 8, 9] : right : [1, 2, 3, 4, 5]
result: [1]
LOOP - left: [6, 7, 8, 9] : right : [1, 2, 3, 4, 5]
result: [1, 2]
LOOP - left: [6, 7, 8, 9] : right : [1, 2, 3, 4, 5]
result: [1, 2, 3]
LOOP - left: [6, 7, 8, 9] : right : [1, 2, 3, 4, 5]
result: [1, 2, 3, 4]
LOOP - left: [6, 7, 8, 9] : right : [1, 2, 3, 4, 5]
result: [1, 2, 3, 4, 5]
result: [1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment