型で1桁の数を quicksort する

quicksort.ts

type SingleDigit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

type Succ<N extends SingleDigit> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0][N]

type EQ<N1, N2> = 
  [N1 extends N2 ? true : false, N2 extends N1 ? true : false] extends [true, true] ? true : false

// N1 < N2
type LT<N1 extends SingleDigit, N2 extends SingleDigit> = 
  Succ<N1> extends 0
    ? false
    : EQ<Succ<N1>, N2> extends true 
      ? true
      : LT<Succ<N1>, N2>

type CollectLT<Arr extends readonly SingleDigit[], N extends SingleDigit> =
  Arr extends [infer X, ...infer Xs]
    ? X extends SingleDigit
      ? [
          ...(LT<X, N> extends true ? [X] : []), 
          ...(Xs extends readonly SingleDigit[] ? CollectLT<Xs, N> : [])
        ]
      : []
    : []

type CollectGTEQ<Arr extends readonly SingleDigit[], N extends SingleDigit> =
    Arr extends [infer X, ...infer Xs]
      ? X extends SingleDigit
        ? [
            ...(LT<X, N> extends false ? [X] : []), 
            ...(Xs extends readonly SingleDigit[] ? CollectGTEQ<Xs, N> : [])
          ]
        : []
      : []

type QuickSort<T extends readonly SingleDigit[]> = T extends [infer Head extends SingleDigit, ...infer Tail extends SingleDigit[]]
  ? Tail extends readonly SingleDigit[]
    ? [
        ...QuickSort<CollectLT<Tail, Head>>,
        Head,
        ...QuickSort<CollectGTEQ<Tail, Head>>
      ]
    : []
  : []


type myArray = [3,1,3,6,5,3,6,5,7,9,0,2,1,3,5,7]


type sorted = QuickSort<myArray>