Answers for "The Merge Sort"

merge sort

MergeSort(arr[], l,  r)
If r > l
     1. Find the middle point to divide the array into two halves:  
             middle m = l+ (r-l)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)

mergesort

def merge_sort(arr):
    if len(arr) > 1:
        middle = len(arr) // 2
        left = arr[:middle]
        right = arr[middle:]

        merge_sort(left)
        merge_sort(right)

        i = len(arr) - 1
        while i >= 0:
            if left and right:
                if left[-1] >= right[-1]:
                    arr[i] = left.pop()
                else:
                    arr[i] = right.pop()
            else:
                arr[i] = left.pop() if left else right.pop()
            i -= 1
    return arr