# Falls left < right ist, mischt die Funktion "merge"
# die sortierten Listen a[left], . . . , a[middle] und
# a[middle+1], . . . , a[right] zu der
# sortierten Liste a[left], . . . , a[right].

def merge(array, left, middle, right):  
     
    left_sublist = array[left:middle + 1]  
    right_sublist = array[middle+1:right+1]  
     
    left_sublist_index = 0  
    right_sublist_index = 0  
    sorted_index = left  
  
    while left_sublist_index < len(left_sublist) and right_sublist_index < len(right_sublist):  
  
        if left_sublist[left_sublist_index] <= right_sublist[right_sublist_index]:  
            array[sorted_index] = left_sublist[left_sublist_index]  
            left_sublist_index = left_sublist_index + 1  
        else:  
            array[sorted_index] = right_sublist[right_sublist_index]  
            right_sublist_index = right_sublist_index + 1  
    
        sorted_index = sorted_index + 1  
   
    while left_sublist_index < len(left_sublist):  
        array[sorted_index] = left_sublist[left_sublist_index]  
        left_sublist_index = left_sublist_index + 1  
        sorted_index = sorted_index + 1  
  
    while right_sublist_index < len(right_sublist):  
        array[sorted_index] = right_sublist[right_sublist_index]  
        right_sublist_index = right_sublist_index + 1  
        sorted_index = sorted_index + 1