# Die Funktion merge(array, left, middle, right) mischt die sortierten Teillisten
# array[left], . . . . , array[middle] und array[middle+1], . . . . , array[right]
# zu der sortierten Gesamtliste  array[left], . . . . , array[right] .
# Quelle: https://www.javatpoint.com/merge-sort-in-python

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