insertion sort recursive

insert_sort_rec.js

// inserts the element at index i into the correct position,
// [0..i-1] must be sorted

function insert_rec(l, i) {
  if (i == 0) return l;
  else {
    if (l[i] < l[i - 1]) {
      return compare_rec(
        [...l.slice(0, i - 1), l[i], l[i - 1], ...l.slice(i + 1)],
        i - 1
      );
    } else {
      return compare_rec(l, i - 1);
    }
  }
}

function insert_sort_rec(l, i) {
  if (i == l.length) return l;
  return insert_sort_rec(insert_rec(l, i), i + 1);
}

console.log(insert_sort_rec([4,5,1,3], 0));