Merge Sort Algorithm

This problem requires you to implement the Merge Sort algorithm. Given an unsorted list of integers, your task is to sort them in ascending order using the Merge Sort methodology. The merge sort algorithm works by dividing the list into two halves, recursively sorting both halves, and then merging the sorted halves to produce the final sorted list.

In mathematical terms, if we denote the merge sort operation by \(MS(\cdot)\) on an array \(A\), then the recurrence relation for merge sort can be written as:

\[ MS(A) = \begin{cases} A, & \text{if } |A| \le 1 \\ merge(\, MS(A_{left}),\, MS(A_{right})\,), & \text{otherwise} \end{cases} \]

The merge operation combines two already sorted lists into a single sorted list.

inputFormat

The input is read from stdin and consists of two lines:

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

outputFormat

Output the sorted list in ascending order to stdout. The numbers should be printed on a single line and separated by a single space.## sample

7
38 27 43 3 9 82 10

3 9 10 27 38 43 82