import pdb
def print_array(arr):
for a in arr:
print a,
def merge(a,b):
i,j = 0,0
merge_array = []
merge_array_cursor = 0
while merge_array_cursor < len(a)+len(b):
if i < len(a):
if j < len(b):
if a[i]< b[j]:
merge_array.append(a[i])
i += 1
else:
merge_array.append(b[j])
j += 1
elif not (j < len(b)):
merge_array.append(a[i])
i += 1
elif not (i < len(a)):
if j < len(b):
merge_array.append(b[j])
j += 1
elif not(j < len(b)):
pass
merge_array_cursor += 1
return merge_array
def merge_sort(array):
if len(array) == 1:
#pdb.set_trace()
return array
new_length = len(array)/2
sub_array1 = merge_sort(array[:new_length])
sub_array2 = merge_sort(array[new_length:])
return merge(sub_array1, sub_array2)
if __name__ == "__main__":
array = [9,-1,1,2,1,3,6,8,7,0]
answer = merge_sort(array) #stupid bug: forgot to take
# the return value from merge_sort(array)
print "answer:"
print_array(answer)
Search This Blog
Thursday, June 11, 2009
Python Merge Sort
#KEY:Visualize the control flow (recursion) and the return value; range checking about the merge process
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment