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)です。さらに、安定ソートアルゴリズムとして知られています。