Merge Sort: Sorting an Array

Given an unsorted array of integers, your task is to sort the array in non-decreasing order using the Merge Sort algorithm. Merge Sort is a classic divide-and-conquer algorithm whose recurrence relation is given by \( T(n)=2T(n/2)+O(n) \). You need to implement the sorting algorithm and output the sorted sequence.

The algorithm works by recursively dividing the array into two halves, sorting each half, and then merging the two sorted halves. Try to achieve an efficient solution that works in \( O(n \log n) \) time complexity.

inputFormat

The input is provided via standard input (stdin) in the following format:

1. The first line contains an integer n, which denotes the number of elements in the array.
2. The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output the sorted array as a single line of space-separated integers to standard output (stdout).

## sample

7
38 27 43 3 9 82 10

3 9 10 27 38 43 82

</p>