def mergesort(items):
    sz = 1

    while sz < len(items):
        result = []
        left_min = 0
        right_min = sz        
        while left_min < len(items):                                
            right_max = min(right_min + sz, len(items))
            
            merged_list = merge(items[left_min:right_min],\
                          items[right_min:right_max])
            result.extend(merged_list)
            
            left_min += 2*sz             
            right_min += 2*sz            
            
        sz = sz * 2
        items = result
        
    return items

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