جواب «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()))))
اول خودت امتحان کن؛ جوابهای دیگر هم قبول است. برگرد و خودت حلش کن