QuickSort Algorithm

Given an array of n integers, your task is to sort the array in ascending order using the QuickSort algorithm. QuickSort is a divide-and-conquer algorithm that works by selecting a pivot element, partitioning the array into two subarrays (elements less than the pivot and elements greater than the pivot), and then recursively sorting the subarrays. The average time complexity of QuickSort is \(O(n \log n)\) and the worst-case time complexity is \(O(n^2)\). Implement the algorithm to correctly sort the given array.

inputFormat

The input is given via stdin in the following format:

• The first line contains a non-negative integer \(n\), which represents the number of elements in the array.
• The second line contains \(n\) space-separated integers.

outputFormat

Output the sorted array to stdout in one line, with each element separated by a single space.

5
1 2 3 4 5

1 2 3 4 5