Merge Sort

You are required to implement the merge sort algorithm to sort a list of integers in non-decreasing order. Merge sort is a classic divide-and-conquer algorithm whose recurrence is given by \(T(n) = 2T(n/2) + \Theta(n)\). In this problem, you need to read an array of integers from standard input, sort it using merge sort, and output the sorted array.

The input begins with a single integer \(n\) (\(0 \le n \le 10^5\)) indicating the number of elements in the array. The next line contains \(n\) space-separated integers. Your task is to output the sorted list with elements separated by a single space.

Note: If \(n = 0\), your program should output nothing.

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\), the number of elements.
• The second line contains \(n\) space-separated integers.

outputFormat

Output a single line containing the \(n\) sorted integers in non-decreasing order, separated by spaces.

## sample

6
3 1 4 1 5 9

1 1 3 4 5 9

</p>