Эффективно сортировать связанный список в Javascript?

Question

Какой самый эффективный способ сортировки связанного списка в Javascript / NodeJS? Если у меня есть массив объектов с id и comesAfter, который ссылается на id предыдущего элемента в списке, как мне его упорядочить?

Функции ES6 в решении хорошо в использовании. И он не должен изменять исходный массив, а возвращать новый. (Но если нетрудно показать, как это сделать на месте, это тоже поможет увидеть.)

// before sorting
[
  { id: "three", comesAfter: "two" },
  { id: "one", comesAfter: null },
  { id: "four", comesAfter: "three" },
  { id: "two", comesAfter: "one" },
]

// after sorting
[
  { id: "one", comesAfter: null },
  { id: "two", comesAfter: "one" },
  { id: "three", comesAfter: "two" },
  { id: "four", comesAfter: "three" },
]

Answer 1

Кажется разумным создать объект, например:

var obj = {};
for (var i = 0; i < input.length; i++) {
    obj[input[i].comesAfter] = input[i];
}

Теперь давайте сгенерируем вывод:

var index = 0;
var output = [obj.null];
while (++index < input.length) {
    output[index] = obj[output[index - 1].id];
}