試したコード

python
## merge sort
import random

def merge_sort(array):
    if len(array) == 1:
        return array

    mid = len(array) // 2
    left = array[0:mid]
    right = array[mid:]
    
    left = merge_sort(left)
    right = merge_sort(right)
    
    return merge(left, right)

def merge(left, right):
    merged = []
    i = 0
    j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1

    if i < len(left):
        merged.extend(left[i:])
    else:
        merged.extend(right[j:])
    return merged


array = [i+1 for i in range(10)]
random.shuffle(array)
merge_sort(array)

References