Merge Sort

Merge sort is one of the fastest sorting algorithms. Many applications use some versions of merge sort in production. We have discussed algorithms that run in quadratic time like Bubble sort or Selection sort. Merge sort is way faster than all the quadratic sorting algorithms and runs in time.

Merge sort is a divide-and-conquer algorithm that recursively sorts parts of the given array and merges those together. The core of the algorithm is the efficient algorithm to merge two sorted arrays into a single sorted array. During its work, the merge sort algorithm splits the array into two parts. Then recursively sorts the first part. After which recursively sorts the second part. Then merges those two sorted arrays into one sorted array:

def merge(a, b):
    i, j, res = 0, 0, []                # Index for a and b with resulting array
    while i < len(a) or j < len(b):     # While there are still elements left
        ai = a[i] if i < len(a) else float('inf')
        bj = b[j] if j < len(b) else float('inf')

        if ai < bj:                     # If a[i] < b[j] => take a[i]
            res.append(ai)              # Add a[i] to result
            i += 1                      # Move to the next element
        else:                           # If a[i] >= b[j] => take b[j]
            res.append(bj)              # Add b[j] to result
            j += 1                      # Move to the next element
    return res


def merge_sort(a):
    if len(a) <= 1:                     # Nothing to sort
        return a                        # Return the initial array

    l = merge_sort(a[: len(a) // 2])    # Sort the left part
    r = merge_sort(a[len(a) // 2:])     # Sort the right part
    return merge(l, r)

At each stage, the algorithm takes the array, splits it into 2 parts, sorts those separately, and merges the resulting arrays into a new one. Note that all the previous algorithms discussed changed the initial array in place (modified it without creating a new one), while the merge sort algorithm creates a new array on each iteration. To make the merge sort algorithm perform an in-place sorting, we would need to modify the algorithm and the merge() function to merge two consecutive blocks of the initial array using only indices. Can you do that 😎?

Let’s simulate the algorithm on several arrays:

[4, 1, -1, 0, 2, 8]

merge_sort([4, 1, -1, 0, 2, 8]):

merge_sort([4, 1, -1])
merge_sort([0, 2, 8])

merge_sort([4, 1, -1]):

merge_sort([4]) → return [4]
merge_sort([1, -1])

merge_sort([1, -1]):

merge_sort([1]) → return [1]
merge_sort([-1]) → return [-1]

Back to merge_sort([1, -1]) → return [-1, 1]

Back to merge_sort([4, 1, -1]) → return [-1, 1, 4]

merge_sort([0, 2, 8]):

merge_sort([0]) → return [0]
merge_sort([2, 8])

merge_sort([2, 8]):

merge_sort([2]) → return [2]
merge_sort([8]) → return [8]

Back to merge_sort([2, 8]) → return [2, 8]

Back to merge_sort([0, 2, 8]) → return [0, 2, 8]

Back to merge_sort([4, 1, -1, 0, 2, 8]) → return [-1, 0, 1, 2, 4, 8]

Challenge

Given an array of n integers, you are asked to sort them in descending order using the Merge Sort algorithm.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000).

The next line contains n space-separated integers ( ≤ ≤ ) representing the initial array.

Output

The program should print n space-separated integers in descending order.

Examples

Input	Output
4 7 4 9 1	9 7 4 1
5 -4 8 2 -3 6	8 6 2 -3 -4

Constraints

Time limit: 2.5 seconds

Memory limit: 512 MB

Output limit: 10 MB