Type-Level Sorting of a Tuple of Numbers

This challenge asks you to implement a generic TypeScript type that can sort a tuple of literal numbers in ascending order at compile time. This is a fun exercise in leveraging TypeScript's advanced type manipulation capabilities to perform computations without running any code.

Problem Description

Your task is to create a TypeScript type SortTuple<T extends readonly number[]> that takes a tuple of literal numbers T and returns a new tuple with the same numbers sorted in ascending order. This sorting must happen entirely within the TypeScript type system.

Key Requirements:

• The input T will be a readonly tuple of number literals (e.g., [3, 1, 4, 2]).
• The output must be a readonly tuple of number literals sorted in ascending order (e.g., [1, 2, 3, 4]).
• The solution should be generic and work for any tuple of numbers.
• The sorting logic should be implemented using conditional types, mapped types, or other type-level constructs.

Expected Behavior:

Given a tuple of numbers, the SortTuple type should produce a new tuple with those numbers arranged from smallest to largest.

Edge Cases to Consider:

• Empty tuple: [] should result in [].
• Tuple with one element: [5] should result in [5].
• Tuple with duplicate numbers: [3, 1, 3, 2] should result in [1, 2, 3, 3].

Examples

Example 1:

type Input1 = [3, 1, 4, 1, 5, 9, 2, 6];
type Output1 = SortTuple<Input1>;
// Expected: [1, 1, 2, 3, 4, 5, 6, 9]

Example 2:

type Input2 = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0];
type Output2 = SortTuple<Input2>;
// Expected: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Example 3:

type Input3 = [];
type Output3 = SortTuple<Input3>;
// Expected: []

Constraints

• The input tuple T will contain only positive or zero integer literal numbers. No floating-point numbers or negative numbers are expected.
• The maximum length of the input tuple will not exceed 10 elements to keep the type computation within reasonable limits for practical use in development.
• The solution should rely solely on TypeScript's type system. No runtime code should be involved in the sorting process.

Notes

This problem is notoriously challenging and often requires thinking recursively. You'll likely need to break down the problem into smaller, solvable parts. Consider how you might:

• Compare two numbers at the type level.
• Remove a specific number from a tuple at the type level.
• Find the smallest number in a tuple at the type level.
• Build the sorted tuple incrementally.

A common approach involves a recursive helper type that repeatedly finds the smallest element, adds it to the result, and then sorts the remaining elements. Good luck!