Median-of-Three QuickSort

Implement the Median-of-Three QuickSort algorithm to sort a list of integers in ascending order.

In this algorithm, the pivot element is chosen as the median of the first, middle, and last elements of the subarray. This can be formally written as: \( \text{median}(a,b,c) \) is the value that is neither maximum nor minimum among \(a\), \(b\), and \(c\). This strategy helps the algorithm perform better on a variety of input cases, including nearly sorted, reverse sorted, or duplicate-heavy lists.

Your task is to implement this algorithm and ensure that the list is sorted correctly. The input will be read from standard input and the sorted list should be printed to standard output as space-separated integers.

inputFormat

The first line contains an integer \(n\), which is the number of integers in the list.

The second line contains \(n\) space-separated integers.

outputFormat

Output a single line with the \(n\) sorted integers in ascending order, separated by a single space.

7
3 6 8 10 1 2 1

1 1 2 3 6 8 10