BFE.devでのAI解答例 - JavaScript コーディング問題
42. Insertion Sortを実装する

以下がJavaScriptでのInsertion Sort実装例です。

function insertionSort(arr) {
  for (let i = 1, len = arr.length; i < len; i++) {
    let j = i - 1;
    let temp = arr[i];
    while (j >= 0 && arr[j] > temp) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = temp;
  }
  return arr;
}

この実装では、配列の一番最初の要素をソート済みにして、次の要素から順に挿入位置を探していくため、時間複雑性はO(n^2)です。また、新たな配列を作成するわけではないため、空間複雑性はO(1)です。さらに、安定ソートアルゴリズムとして知られています。