بتل کد Battle Codeدارد باز می‌شود…

جواب «Merge Sort» چالش 6 از جلسه‌ی 33

سؤال

تابع بازگشتی merge_sort(a) بنویسید که لیست جدیدِ مرتب برگرداند (لیست را نصف کنید، هر نیمه را مرتب و سپس ادغام کنید). یک خط اعداد صحیح بخوانید و نتیجه را با فاصله چاپ کنید. از sorted، .sort و heapq استفاده نکنید.

راهنما

حالت پایه: لیست با طول کمتر از ۲ خودش مرتب است. ادغام را در یک تابع جدا بنویسید.

یک جواب درست

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


def merge_sort(a):
    if len(a) < 2:
        return a
    mid = len(a) // 2
    return merge(merge_sort(a[:mid]), merge_sort(a[mid:]))


print(*merge_sort(list(map(int, input().split()))))

اول خودت امتحان کن؛ جواب‌های دیگر هم قبول است. برگرد و خودت حلش کن