Merge Sort

merge_sort.py

def merge(left, right):
    result = []
    i ,j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result += left[i:]
    result += right[j:]
    return result

def mergesort(arr):
	arr_len = len(arr)
	flag=0
	for i in range(0,arr_len-1):
		if(arr[i]>arr[i+1]):
			flag=1
			left = mergesort(arr[:i+1])
			right = mergesort(arr[i+1:])
			return merge(left,right)
	if(flag!=1):
		return merge(arr,[])
print mergesort([2,3,1,6,4,5,9,22,1,33,12,65,78])