valiv

посмотрите пропсы у react-router, у них есть что-то типа basePath

Собираем вспомогательный объект вида { key: первый индекс, где встречается key }:

const keyIndex = arr.reduce((acc, n, i) => (acc[n.key] ??= i, acc), {});

Затем выполняем сортировку по двум параметрам, минимальному индексу и id. Можно отсортировать существующий массив:

arr.sort((a, b) => (keyIndex[a.key] - keyIndex[b.key]) || (a.id - b.id));

Или собрать отсортированный новый:

const sorted = (arr, keys) => arr
  .map(n => [ n ].concat(keys(n)))
  .sort((a, b) => {
    let diff = 0;
    for (let i = 0; ++i < a.length && !(diff = a[i] - b[i]);) ;
    return diff;
  })
  .map(n => n[0]);


const sortedArr = sorted(arr, n => [ keyIndex[n.key], n.id ]);

Пройти по массиву, складывая встреченные новые ключи в массив уникальных ключей в порядке их встречи.
Индекс ключа в этом массиве и id элемента становятся ключами для сортировки.
Отсортировать (но не взбалтывать!) и удалить добавленный сортировочный ключ.

const dict = [];
arrObj.forEach((el, i) => {
  if (! dict.includes(el.key)) dict.push(el.key);
  el.sorter = dict.indexOf(el.key);
});
arrObj.sort((a, b) => a.sorter < b.sorter ? -1 : (a.sorter > b.sorter ? 1 : a.id - b.id));
arrObj.forEach((el) => delete el.sorter);

console.log(arrObj);