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

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)

No comments: