Hybrid Sorting Algorithm

You are given an array of n integers and a threshold value T. Your task is to sort the array in ascending order using the HybridSort algorithm.

The HybridSort algorithm works as follows:

• If the number of elements in the array is less than or equal to T, use Insertion Sort to sort the array.
• If the number of elements is greater than T, use a QuickSort-style partitioning approach by selecting the middle element as the pivot, partitioning the array into three parts (less than, equal to, and greater than the pivot) and then recursively sorting the left and right partitions.

The recurrence for this hybrid algorithm can be illustrated by the following latex formula:

\(T(n) = \begin{cases} O(n^2) & \text{if } n \leq T,\\ T(\lfloor \frac{n}{2} \rfloor) + T(\lceil \frac{n}{2} \rceil) + O(n) & \text{if } n > T. \end{cases}\)

Implement the HybridSort algorithm, ensuring that all edge cases (such as an array with a single element) are handled correctly.

inputFormat

The input is given via standard input (stdin) and has the following format:

n T
a1 a2 a3 ... an

Here, n is the number of elements in the array, T is the threshold for deciding the sorting method, and a1, a2, ..., an are the integers in the array.

outputFormat

Output the sorted array in ascending order as a sequence of integers separated by spaces on a single line to standard output (stdout).

## sample

8 4
12 4 5 6 7 3 1 15

1 3 4 5 6 7 12 15