mergesort.ts

const head = <A>(l: A[]) => l[0];
const tail = <A>(l: A[]) => l.slice(1);
const splitList = <A>(l: A[]) => [l.slice(0, l.length / 2), l.slice(l.length / 2)];


export const mergeSortedLists = (a: number[], b: number[], accumulator: number[] = []): number[] => {
  if (a.length === 0) {
    return [...accumulator, ...b];
  }
  if (b.length === 0) {
    return [...accumulator, ...a];
  }
  return mergeSortedLists(
    head(a) <= head(b) ? tail(a) : a,
    head(a) > head(b) ? tail(b) : b,
    [...accumulator, Math.min(head(a), head(b))]
  );
};

export const mergesort = (l: number[]): number[] =>
  l.length <= 1 
  ? l 
  : mergeSortedLists(
    ...(splitList(l).map(mergesort) as [number[], number[]])
  );