Сортировка слиянием

# merge sort
print_timing
def merge_sort(list2):
merge_sort_r(list2, 0, len(list2) -1)
 
# merge sort recursive (used by merge_sort)
def merge_sort_r(list2, first, last):
if first < last:
sred = (first + last)/2
merge_sort_r(list2, first, sred)
merge_sort_r(list2, sred + 1, last)
merge(list2, first, last, sred)
 
# merge (used by merge_sort_r)
def merge(list2, first, last, sred):
helper_list = []
i = first
j = sred + 1
while i <= sred and j <= last:
if list2 [i] <= list2 [j]:
helper_list.append(list2[i])
i += 1
else:
helper_list.append(list2 [j])
j += 1
while i <= sred:
helper_list.append(list2[i])
i +=1
while j <= last:
helper_list.append(list2[j])
j += 1
for k in range(0, last - first + 1):
list2[first + k] = helper_list [k]

"""Merge sort."""
 
def merge(left, right):
    """Merge two lists in ascending order."""
    lst = []
    while left and right:
        if left[0] < right[0]:
            lst.append(left.pop(0))
        else:
            lst.append(right.pop(0))
    if left:
        lst.extend(left)
    if right:
        lst.extend(right)
    return lst
 
def mergesort(lst):
    """Sort the list by merging O(n * log n)."""
    length = len(lst)
    if length >= 2:
        mid = int(length / 2)
        lst = merge(mergesort(lst[:mid]), mergesort(lst[mid:]))
    return lst

>>> print(''.join(mergesort(list("defgaabcdef"))))
aabcddeeffg
>>> print(''.join(mergesort(list("12348723400023498234"))))
00012222333344447889
>>>