Sorting Algorithms Comparison

In this problem, you are required to implement two classic sorting algorithms: QuickSort and MergeSort. Given a list of n integers, your task is to sort the list in non-decreasing order using both algorithms.

The QuickSort algorithm is a divide-and-conquer method with an average time complexity of \(O(n \log n)\) but may degrade to \(O(n^2)\) in the worst-case scenario. On the other hand, MergeSort consistently runs in \(O(n \log n)\) time due to its stable splitting and merging process.

You must output the results of both sorts in a specific format. First, print "QuickSort", followed by the sorted list produced by your QuickSort implementation. Then, print "MergeSort", followed by the sorted list produced by your MergeSort implementation.

Note: Your implementation must read the input from standard input (stdin) and write the output to standard output (stdout).

inputFormat

The input consists of two lines:

1. The first line contains an integer (n) ((1 \le n \le 10^5)) representing the number of integers.
2. The second line contains (n) space-separated integers.

outputFormat

The output should consist of four lines:

1. The first line prints the string "QuickSort".
2. The second line prints the sorted list (using QuickSort) as space-separated integers.
3. The third line prints the string "MergeSort".
4. The fourth line prints the sorted list (using MergeSort) as space-separated integers.## sample

6
3 -1 4 1 5 9

QuickSort
-1 1 3 4 5 9
MergeSort
-1 1 3 4 5 9