Вопрос проверяет понимание алгоритма сортировки слиянием, его принципа работы и временной сложности, что важно для оценки навыков алгоритмического мышления.
Сортировка слиянием (Merge Sort) — это эффективный алгоритм сортировки, основанный на принципе «разделяй и властвуй». Он рекурсивно разбивает исходный массив на две равные части до тех пор, пока каждая часть не будет состоять из одного элемента (такой массив считается отсортированным). Затем происходит слияние этих частей в правильном порядке.
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
let result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) result.push(left[i++]);
else result.push(right[j++]);
}
return result.concat(left.slice(i)).concat(right.slice(j));
}Сортировка слиянием часто используется для сортировки больших объёмов данных, особенно когда важна стабильность (сохранение порядка равных элементов) и предсказуемая производительность. Она также применяется во внешних сортировках, когда данные не помещаются в оперативную память.
Вывод: Сортировка слиянием — надёжный выбор для задач, где требуется гарантированная производительность O(n log n) и стабильность, но стоит учитывать её потребление дополнительной памяти.
