insertsort.ts

insertsort.ts

// this i got the idea from this issue https://github.com/type-challenges/type-challenges/issues/8168
type GreaterThan<
  T extends number,
  U extends number,
  C extends unknown[] = []
  > =
  T extends U
    ? false
    : C['length'] extends T
      ? false
      : C['length'] extends U
        ? true
        : GreaterThan<T, U, [...C, 1]>;

const a: GreaterThan<9, 0> // true
const a: GreaterThan<0, 9> // false
const a: GreaterThan<0, 0> // false

      
      // used this issue as idea to make a insert sort https://github.com/type-challenges/type-challenges/issues/856
type Insert<
  N extends number,
  A extends Array<any>,
  > =
  A extends [infer C, ...infer R]
    ? GreaterThan<N, C> extends false
      ? [N, ...A]
      : [C, ...Insert<N, R>]
    : [N]

type Sort<
  V extends Array<number>,
  A extends Array<any> = []
  > =
  V extends [infer C, ...infer R]
    ? Sort<R, Insert<C, A>>
    : A

let t: Sort<[2, 2, 1, 5, 6]>; // [1, 2, 2, 5, 6]
let t: Sort<[5, 20, 10000000002, 1, 25]>; // [1, 5, 20, 25, 10000000002]
let t: Sort<[5, 20, 121, 1, 25, 26, 512]>; // [1, 5, 20, 25, 26, 121, 512]

/**
 * Explanation:
 * Sort has an accumulator and the array that is being sorted,
 * first we get the element at index 0 and call it C as current and the rest as R
 * then whe pass first element of the array(C) to helper type called Insert that uses the C element and the Accumulator(A)
 * Insert uses the first value passed as N and the sort accumulator as A.
 * It makes the same infer pattern as Sort does then it compares the first value of A with N
 * if it is false it pushes N as first and then places the values of the Accumulator as last;
 * if it is true it pushes C as first and then calls Insert again with N and the rest of the array (R);
 * when this fails, it returns the value of N;
 * Sort does this until infer array pattern fails then it returns the Accumulator that was sorted
 *
 * this in js:
 *
 * function sort(arr) {
 *   for (let i = 1; i < arr.length; i++) {
 *     // First, choose the element at index 1
 *     let current = arr[i];
 *     let j;
 *
 *     for (j = i - 1; j >= 0 && arr[j] > current; j--) {
 *       // as long as arr[j] is bigger than current
 *       // move arr[j] to the right at arr[j + 1]
 *       arr[j + 1] = arr[j];
 *     }
 *     // Place the current element at index 0
 *     // or next to the smaller element
 *     arr[j + 1] = current;
 *   }
 *   return arr;
 * }
 */