QuickSort: Efficient Array Sorting

Implement the QuickSort algorithm to sort an array of integers in ascending order. QuickSort is a classic divide-and-conquer algorithm that works as follows:

• Select a pivot element from the array.
• Partition the array into two subarrays: one with elements less than the pivot and the other with elements greater than the pivot.
• Recursively apply the above steps on the subarrays.

The recurrence relation for QuickSort is given by \(T(n) = T(k) + T(n-k-1) + \Theta(n)\), where \(k\) is the number of elements in one partition.

Your task is to implement the QuickSort algorithm. If the input array is empty, your program should output nothing.

inputFormat

The input consists of two lines:

1. The first line contains an integer \(n\) (\(0 \leq n \leq 10^5\)) representing the number of elements in the array.
2. If \(n > 0\), the second line contains \(n\) space-separated integers.

outputFormat

Output the sorted array in ascending order as a single line with each integer separated by a single space. If \(n = 0\), output nothing.

1
1

1