Quick Sort Problem Statement

You are given an array of integers. Your task is to sort this array in ascending order using the Quick Sort algorithm.

Quick Sort utilizes a divide and conquer approach where a pivot is chosen and the array is partitioned into two parts. The left part contains elements smaller than the pivot, and the right part contains elements larger than the pivot. This process is repeated recursively on both parts until the entire array is sorted.

Example:

Input:

array = [4, 2, 1, 5, 3]

Output:

[1, 2, 3, 4, 5]

Explanation:

If the rightmost number is chosen as pivot, after the first partition, the array will be [2, 1, 3, 4, 5]. After recursive partitioning, the final sorted array will be [1, 2, 3, 4, 5].

Constraints:

• 1 <= T <= 10
• 1 <= N <= 10³
• -10⁹ <= ARR[i] <= 10⁹

Input Format:

The first line of input contains an integer 'T' denoting the number of test cases.
Each test case consists of two lines:
1. An integer 'N' denoting the number of elements in the array.
2. 'N' space-separated integers denoting the elements of the array.

Output Format:

For each test case, output a single line containing the sorted array, with elements separated by spaces.

Note:

No need to print anything, just implement the given function.

Follow Up:

Can you solve this in the worst-case complexity of NlogN?