merge_sort.py

defmerge_sort(values):
iflen(values) <=1:
returnvalues
else:
middle_index=len(values) //2

left_half=merge_sort(values[:middle_index])
right_half=merge_sort(values[middle_index:])

sorted_values= []
left_index=0; right_index=0

whileleft_index<len(left_half) andright_index<len(right_half):
ifleft_half[left_index] <=right_half[right_index]:
sorted_values.append(left_half[left_index])
left_index+=1
else:
sorted_values.append(right_half[right_index])
right_index+=1


sorted_values+=left_half[left_index:]
sorted_values+=right_half[right_index:]

returnsorted_values