Challenge: Write Merge Sort

Lab Python Intermediate 20 points

Read a list of numbers and sort it with your own merge sort (no sort/sorted). Print the sorted numbers separated by spaces.

Input

One line of whole numbers.

Output

The sorted numbers.

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

Base case: a list of 0 or 1 items is sorted.

Split at mid, sort both halves, then merge with two pointers.

Solution explanation

log n levels of splitting, n work per level: O(n log n).

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:])
    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:]

print(" ".join(map(str, merge_sort(list(map(int, input().split()))))))

Output

Answer