Merge Sort Algorithm

This problem requires you to implement the Merge Sort algorithm to sort an array of integers in non-decreasing order. Merge Sort is a classic divide and conquer algorithm with a time complexity of \(O(n \log n)\) and a space complexity of \(O(n)\). In this problem, you will receive the unsorted list of integers via standard input and are expected to output the sorted list on standard output.

The algorithm works by recursively splitting the array into halves until a single element is left, and then merging these halves in a sorted manner. This method ensures that the final merged list is fully sorted.

inputFormat

The first line of input contains an integer \(n\) — the number of elements in the array. The second line contains \(n\) integers separated by spaces.

Example:

5
3 1 4 5 2

outputFormat

Output the sorted array as a sequence of \(n\) integers separated by a single space on one line.

Example:

1 2 3 4 5

5
1 2 3 4 5

1 2 3 4 5