Merge Sort

Lab Python Advanced 30 points

Implement recursive merge sort and print the sorted list.

Input

One line of integers.

Output

One line.

Example

Input

38 27 43 3 9 82 10

Output

3 9 10 27 38 43 82

Sample input available Sample output available

Editor

Python

Hints

Split in half, sort each half recursively, then merge.

Solution explanation

Merge sort always runs in O(n log n) and is stable (equal items keep their order).

Show solution

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    merged, i, j = [], 0, 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
    return merged + left[i:] + right[j:]


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

Output

Answer