再帰的挿入予期しないスタックでソートする

Question

InsertionSortを再帰的に記述しようとしていますが、次のコードを思いつきました。

function recursiveInsertionSort(array) { 
    sort(array, array.length - 1); 
} 

function sort(array, index) { 
    if (index > 0) { 
     sort(array, index - 1); 
     let j = index - 1; 
     let key = array[index]; 
     while (j >= 0 && array[j] > key) { 
      array[j + 1] = array[j]; 
      j--; 
     } 
     array[j + 1] = key; 
    } 
} 

このコードは完全に動作しています。

たとえば、入力が[4, 1, 3, 2, 16, 9, 10, 14, 8, 7]の場合、その戻り値は[1, 2, 3, 4, 7, 8, 9, 10, 14, 16]です。

私は、現在のインデックスに値を一時変数に格納してループ内で使用しようとしています。

変数に格納するのではなく、次のコードのように直接使用すると出力が間違っています。つまり、配列はソートされません。なぜそれがそのように振る舞っているのか分からなかった。再帰スタックさえ私にとって完璧なようです。しかし、私は奇妙な出力を得ています。例えば

function sort(array, index) { 
    if (index > 0) { 
     sort(array, index - 1); 
     let j = index - 1; 
     while (j >= 0 && array[j] > array[index]) { 
      array[j + 1] = array[j]; 
      j--; 
     } 
     array[j + 1] = array[index]; 
    } 
} 

入力[4, 1, 3, 2, 16, 9, 10, 14, 8, 7]ある場合、それは[ 4, 4, 4, 4, 16, 16, 16, 16, 16, 16 ]を返します。

私はこれを手伝ってもらえますか？これは実際に私の再帰の理解を粉砕しています。

Answer 1

array[index]は、最初のステップで変更されています。（jがindex - 1とき）

j = index -1 
array[j+1] = array[j] => array[index]= array[index-1] 

ですから、keyへarray[index]を保存しない場合は、ソートするとき、あなたはデータを失うことになります。