Как отсортировать массив на месте с учетом массива целевых индексов?

Как бы вы отсортировали данный массивarr на месте дан массив целевых показателейind?

Например:

var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [ 4,   0,   5,   2,   1,   3 ];

rearrange(arr, ind);

console.log(arr); // => ["B", "E", "D", "F", "A", "C"]

arr = ["A", "B", "C", "D"];
ind = [ 2,   3,   1,   0 ];

rearrange(arr, ind);

console.log(arr); // => ["D", "C", "A", "B"]

Я попробовал следующий алгоритм, но он не работает на втором примере выше.

function swap(arr, i, k) {
  var temp = arr[i];
  arr[i] = arr[k];
  arr[k] = temp;
}

function rearrange(arr, ind) {
  for (var i = 0, len = arr.length; i < len; i++) {
    if (ind[i] !== i) {
      swap(arr, i, ind[i]);
      swap(ind, i, ind[i]);
    }
  }
}

Как бы вы решили это за O (n) время и O (1) дополнительное пространство?

Не могли бы вы предоставить доказательство того, что ваш алгоритм работает?

Замечания: Этот вопрос выглядит какэтотно тут мутируетind позволено.

Ответы на вопрос(7)

Ваш ответ на вопрос