Type-Level Quick Sort in TypeScript

This challenge focuses on implementing the Quick Sort algorithm entirely at the TypeScript type level. You will leverage advanced TypeScript features like conditional types, mapped types, and variadic tuple types to sort a tuple of numbers without executing any runtime code. This is a great exercise for understanding the expressive power of TypeScript's type system.

Problem Description

Your task is to create a TypeScript type, QuickSort<T>, that takes a tuple of numbers T and returns a new tuple with the same numbers sorted in ascending order. The sorting must be achieved purely through type manipulation.

Key requirements:

• Type-Level Only: No runtime JavaScript code should be involved in the sorting process. The entire logic must be within the TypeScript type definitions.
• Input: A tuple of numbers (e.g., [3, 1, 4, 1, 5, 9, 2, 6]).
• Output: A new tuple containing the same numbers as the input, but sorted in ascending order.
• Generic: The type should work for any tuple of numbers within the limits of TypeScript's type recursion depth.
• Pivot Selection: You can choose any reasonable pivot selection strategy (e.g., the first element).

Expected behavior:

The QuickSort type should recursively partition the input tuple based on a chosen pivot, sort the sub-partitions, and then concatenate them.

Edge cases:

• Empty tuple: [] should result in [].
• Tuple with one element: [5] should result in [5].
• Tuples with duplicate elements.

Examples

Example 1:

type InputTuple1 = [3, 1, 4, 1, 5, 9, 2, 6];
type SortedTuple1 = QuickSort<InputTuple1>;
// Expected Output: [1, 1, 2, 3, 4, 5, 6, 9]

Example 2:

type InputTuple2 = [9, 8, 7, 6, 5, 4, 3, 2, 1];
type SortedTuple2 = QuickSort<InputTuple2>;
// Expected Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Example 3:

type InputTuple3 = [5];
type SortedTuple3 = QuickSort<InputTuple3>;
// Expected Output: [5]

Example 4:

type InputTuple4 = [];
type SortedTuple4 = QuickSort<InputTuple4>;
// Expected Output: []

Constraints

• The input T will always be a tuple of number types.
• The numbers in the tuple will be non-negative integers.
• The depth of type recursion should be managed; extremely large tuples might hit TypeScript's recursion limits.
• You may need helper types for partitioning and concatenation.

Notes

This challenge requires a deep understanding of TypeScript's conditional types, infer keywords, and variadic tuple types. You'll likely need to define helper types to manage the partitioning logic (elements less than pivot, elements greater than or equal to pivot) and then recursively apply QuickSort to these partitions. Consider how to handle the base cases for the recursion (empty or single-element tuples). Good luck!