Merge Sort Implementation

You are given an array of n integers. Your task is to implement the Merge Sort algorithm to sort the array in non-decreasing order.

The merge sort algorithm is a classic divide and conquer algorithm. It recursively divides the array into two halves, sorts each half, and then merges the two sorted halves. The time complexity of merge sort is \(O(n \log n)\), making it efficient for large data sets.

Note: All formulas are written in \(\LaTeX\) format. For example, the time complexity is given as \(O(n \log n)\).

inputFormat

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

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

For example:

5
12 11 13 5 6

outputFormat

The output is written to stdout. It should contain the sorted array with the elements separated by a single space.

For example, for the input above, the output should be:

5 6 11 12 13

## sample

5
12 11 13 5 6

5 6 11 12 13