Merge Sort Implementation

Given an array of integers, implement the merge sort algorithm to sort the array in non-decreasing order. Merge sort is a classic divide and conquer algorithm. The array should be split into two halves, recursively sorted, and then merged. The midpoint is computed as \( mid = \lfloor \frac{n}{2} \rfloor \), where \( n \) is the number of elements in the array.

Your program should read the input from standard input (stdin) and output the results to standard output (stdout). It must handle various edge cases including empty arrays and arrays with duplicate or large numbers.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer \( n \) representing the number of elements in the array.
• If \( n > 0 \), the second line contains \( n \) space-separated integers.

outputFormat

Output the sorted array as space-separated integers in one line. If the array is empty, output nothing.

0