Monocarp's Sorting Algorithm

Monocarp's Sorting Algorithm is a recursive algorithm that sorts arrays using a modified quick sort technique. The pivot element is chosen as the middle element of the array, and the array is partitioned into three parts: those less than the pivot, those equal to the pivot, and those greater than the pivot. The recurrence relation for the running time can be expressed as: $$T(n)=T(k)+T(n-k-1)+O(n)$$, where $$k$$ represents the number of elements in one partition. Your task is to implement this sorting algorithm and process multiple test cases.

inputFormat

The first line of input contains an integer $$t$$, representing the number of test cases. For each test case, the first line contains an integer $$n$$, the number of elements in the array. The next line contains $$n$$ space-separated integers.

outputFormat

For each test case, output a single line containing the sorted array in ascending order. The numbers must be separated by a space.

3
5
3 1 4 1 5
7
10 20 30 40 50 60 70
4
2 8 6 4

1 1 3 4 5
10 20 30 40 50 60 70
2 4 6 8