​

function insertionSort(numbers) {

  let lastNumber;

  let lastNumberIsSorted = false;

  // base case

  if (numbers.length === 0) {

    return numbers;

  }

  // recursive step

  else {

    lastNumber = numbers.pop();

    // magic!

    insertionSort(numbers);

​

    // insert popped number into sorted array

    for (let i = numbers.length - 1; i >= 0; i--) {

      if (lastNumber < numbers[i]) {

        numbers[i + 1] = numbers[i];

      }

      else {

        numbers[i + 1] = lastNumber;

        lastNumberIsSorted = true;

        break;

      }

    }

    if (!lastNumberIsSorted) {

      numbers[0] = lastNumber;

    }

    return numbers;

  }

}

​

// test

let testNumbers = [25, 8, 28, 4, 28, 9];

console.log(insertionSort(testNumbers)); // expect [4, 8, 9, 25, 28, 28]