Optimized Sort

In this problem, you are required to implement an efficient sorting algorithm to sort a list of integers which may include both positive and negative numbers. The algorithm should work correctly and efficiently even for large datasets.

Task: Given an integer n followed by n space-separated integers, output the sorted sequence in ascending order.

Note: The input will be given via stdin and the output should be printed to stdout.

The expected time complexity in the worst case is \(O(n \log n)\). You can use any efficient sorting algorithm (for example, Timsort, which is also used by Python's built-in sorted() function).

inputFormat

The first line contains a single integer \(n\) representing the number of integers.

The second line contains \(n\) space-separated integers, which may include both positive and negative numbers.

outputFormat

Output a single line containing the sorted \(n\) integers in ascending order. The numbers should be space-separated.

7
4 -1 7 -3 2 -6 5

-6 -3 -1 2 4 5 7