Sort

Sort<T> takes a tuple of natural numbers and returns them in ascending order. A second parameter flips the direction: when it is true, the result comes back descending. Duplicates stay, and the empty tuple sorts to itself.

Sort<[]> // []
Sort<[1]> // [1]
Sort<[2, 4, 7, 6, 6, 6, 5, 8, 9]> //  [2, 4, 5, 6, 6, 6, 7, 8, 9]
 
Sort<[3, 2, 1], true> // [3, 2, 1]
Sort<[3, 2, 0, 1, 0, 0, 0], true> // [3, 2, 1, 0, 0, 0, 0]

Sorting is the familiar part. The obstacle is that numeric literal types cannot be compared: extends on two number literals only ever answers "are these the same literal". Everything below is built on one substitute for the missing comparison operator.

Sort<[]> // []
Sort<[1]> // [1]
Sort<[2, 4, 7, 6, 6, 6, 5, 8, 9]> //  [2, 4, 5, 6, 6, 6, 7, 8, 9]

Sort<[3, 2, 1], true> // [3, 2, 1]
Sort<[3, 2, 0, 1, 0, 0, 0], true> // [3, 2, 1, 0, 0, 0, 0]

/* _____________ Your Code Here _____________ */

type Sort<T extends number[], Descending extends boolean = false> = any

/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '../helpers'

type cases = [
  Expect<Equal<Sort<[]>, []>>,
  Expect<Equal<Sort<[1]>, [1]>>,
  Expect<Equal<Sort<[2, 1]>, [1, 2]>>,
  Expect<Equal<Sort<[0, 0, 0]>, [0, 0, 0]>>,
  Expect<Equal<Sort<[1, 2, 3]>, [1, 2, 3]>>,
  Expect<Equal<Sort<[3, 2, 1]>, [1, 2, 3]>>,
  Expect<Equal<Sort<[3, 2, 1, 2]>, [1, 2, 2, 3]>>,
  Expect<Equal<Sort<[3, 2, 0, 1, 0, 0, 0]>, [0, 0, 0, 0, 1, 2, 3]>>,
  Expect<E

Detailed Explanation

The solution in full:

type Tuple<
  N extends number,
  Acc extends unknown[] = [],
> = Acc['length'] extends N ? Acc : Tuple<N, [...Acc, unknown]>
 
type LessOrEqual<A extends number, B extends number> =
  Tuple<B> extends [...Tuple<A>, ...unknown[]] ? true : false
 
type Insert<N extends number, T extends number[]> = T extends [
  infer Head extends number,
  ...infer Rest extends number[],
]
  ? LessOrEqual<N, Head> extends true
    ? [N, ...T]
    : [Head, ...Insert<N, Rest>]
  : [N]
 
type Ascending<T extends number[], Acc extends number[] = []> = T extends [
  infer Head extends number,
  ...infer Rest extends number[],
]
  ? Ascending<Rest, Insert<Head, Acc>>
  : Acc
 
type Reverse<T extends number[], Acc extends number[] = []> = T extends [
  infer Head extends number,
  ...infer Rest extends number[],
]
  ? Reverse<Rest, [Head, ...Acc]>
  : Acc
 
type Sort<
  T extends number[],
  Descending extends boolean = false,
> = Descending extends true ? Reverse<Ascending<T>> : Ascending<T>

Read it bottom-up: Sort sorts ascending and then reverses if asked, Ascending is insertion sort, and Insert leans on LessOrEqual, which is where the interesting work happens.

Turning a number into a length

Tuple<N> builds a tuple with exactly N elements, one unknown at a time, so that Tuple<3> is [unknown, unknown, unknown] and Tuple<0> is [].

Acc starts empty and grows on every step, and Acc['length'] on a tuple is a literal number type rather than the general number, which gives the base case something to check against N. Both branches are either Acc or the bare recursive call with nothing wrapped around it, the shape TypeScript unrolls without stacking frames.

Once a number is a length, comparison is a shape question. A <= B holds exactly when a tuple of length B begins with A elements:

// LessOrEqual<2, 3> is true   [u, u, u]    matches [u, u, ...unknown[]]
// LessOrEqual<3, 2> is false  [u, u]       is too short to match [u, u, u, ...]
// LessOrEqual<2, 2> is true   the rest matches the empty remainder

The trailing ...unknown[] is what makes this a prefix test instead of an equality test. It absorbs any number of leftover elements, including none, so the equal case answers true as well.

Placing one number into a sorted tuple

Insert<N, T> assumes T is already sorted and returns it with N in the right place. The pattern [infer Head extends number, ...infer Rest extends number[]] splits a tuple into its first element and everything after it. The extends number clauses on the infer are not decoration: without them Head would be unknown, and LessOrEqual would refuse it.

If N belongs before Head, the whole of T is spliced back on: [N, ...T]. Otherwise Head stays in front and the search continues in Rest. When the tuple runs out, N was larger than everything and becomes the last element.

// Insert<2, [1, 3]> is [1, 2, 3]
// Insert<5, [1, 3]> is [1, 3, 5]

[Head, ...Insert<N, Rest>] wraps the recursive call, so this one is not tail-recursive. That is fine here: its depth is bounded by the length of the tuple, not by the size of the numbers in it.

Carrying the result forward

Ascending walks the input once and hands each element to Insert. The sorted-so-far result travels forward as a second type parameter rather than being assembled on the way back out:

// Ascending<[3, 2, 1]> with Acc = []
// step 1: Ascending<[2, 1], Insert<3, []>>   Acc = [3]
// step 2: Ascending<[1],    Insert<2, [3]>>  Acc = [2, 3]
// step 3: Ascending<[],     Insert<1, [2, 3]>> Acc = [1, 2, 3]
// input empty, return Acc

That accumulator style is what keeps the outer walk tail-recursive. The empty input falls straight through to Acc, which is why Sort<[]> is [] with no special case.

Descending for free

Reverse is the same accumulator trick with the head pushed onto the front of Acc instead of appended. Reversing an ascending sort is a correct descending sort, because equal values are interchangeable.

One limit worth knowing: Tuple<N> builds an actual N-element tuple, so comparison tops out in the low thousands. The upstream extra challenge about 15-digit numbers needs a comparator that works digit by digit on strings. Only LessOrEqual would change, the rest stays.

Edge cases the tests cover

• Sort<[]> and Sort<[], true> are both []. The input never matches the head pattern, so the empty accumulator is returned as-is.
• Sort<[0, 0, 0]> keeps all three zeros. LessOrEqual<0, 0> is true, so each new zero lands in front of the previous one, and three identical elements come out identical.
• Sort<[1, 1, 2, 1, 1, 1, 1, 1, 1]> is the duplicate-heavy case: every 1 stops at the very first position, and only the 2 walks to the end.
• Sort<[3, 2, 1, 2], true> is [3, 2, 2, 1]. Ascending gives [1, 2, 2, 3] and the reverse pass mirrors it.
• Sort<[2, 4, 7, 6, 6, 6, 5, 8, 9]> is the longest input, nine elements with a run of three sixes, and costs at most nine Insert walks.