Вставка отсортированных данных в JS
Когда я лет 10 назад писал на C++, то помню, как использовал структуру std:set чтобы сразу упорядоченно вставлять данные в массив. В JavaScript похожий Set завезли, но к сожалению компаратор в него не вставить. Придется засучить рукава и писать все самому. export function pushSortable<T>( list: T[], item: T, comparator: (a: T, b: T) => -1 | 0 | 1 ) { // находим позицию первого элемента который больше вставляемого const index = list.findIndex(list, item, (a, b) => comparator(a, b) === -1); // если не находим то добавляем в конец if (index < 0) { list.push(item); return; } // последовательно сдвигаем элементы на 1 позицию влево let tmp = item; for (let i = index, iLen = list.length; i <= iLen; i++) { tmp = list[i]; list[i] = item; item = tmp; } } На этом можно было бы остановиться. Но анализируя на сложность подобного решения, выясняется что findIndex - это O(N), а сдвиг элементов O(N). И если сдвиг элементов ускорить не получиться, то поиск можно заменить на бинарный и улучшить сложность до O(log N). ...