Implement and Compare Quicksort and Mergesort

In this problem, you are required to implement two famous sorting algorithms: Quicksort and Mergesort. You will use helper functions for partitioning and merging respectively. Given an array of integers, your task is to sort the array in ascending order using both algorithms. Additionally, you should output the efficiency analysis for each algorithm in LaTeX format. For example, the time complexities should be represented as: $O(n \log n)$ for average cases and $O(n^2)$ or $O(n \log n)$ for worst cases. This problem not only tests your ability to implement recursive sorting algorithms but also your understanding of their performance characteristics.

inputFormat

The input is given via standard input (stdin). The first line contains an integer n representing the number of elements in the array. The second line contains n space-separated integers.

outputFormat

The output should be printed to standard output (stdout) and consist of four lines:

1. The first line is the sorted array using Quicksort (elements separated by a single space).
2. The second line is the sorted array using Mergesort (elements separated by a single space).
3. The third line is the efficiency analysis for Quicksort in the format: Quicksort: Average Case: $O(n \log n)$, Worse Case: $O(n^2)$.
4. The fourth line is the efficiency analysis for Mergesort in the format: Merge Sort: Average Case: $O(n \log n)$, Worse Case: $O(n \log n)$.## sample

9
3 7 8 5 2 1 9 5 4

1 2 3 4 5 5 7 8 9
1 2 3 4 5 5 7 8 9
Quicksort: Average Case: $O(n \log n)$, Worse Case: $O(n^2)$
Merge Sort: Average Case: $O(n \log n)$, Worse Case: $O(n \log n)$