Этот вопрос проверяет понимание алгоритма сортировки слиянием, его временной сложности и принципа "разделяй и властвуй", что важно для оценки навыков алгоритмического мышления.
Сортировка слиянием (merge sort) — это классический алгоритм сортировки, который использует подход "разделяй и властвуй". Основная идея заключается в том, чтобы разбить исходный массив на более мелкие части, отсортировать их и затем объединить в один отсортированный массив. Этот алгоритм гарантирует стабильную производительность O(n log n) независимо от входных данных, что делает его предпочтительным для больших наборов данных.
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]);
i++;
} else {
result.push(right[j]);
j++;
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}Сортировка слиянием широко используется в ситуациях, где важна стабильность и предсказуемая производительность, например, при сортировке больших файлов или в базах данных. Однако из-за дополнительных затрат памяти она менее эффективна для малых массивов по сравнению с быстрой сортировкой. Вывод: применяйте merge sort, когда требуется гарантированная временная сложность O(n log n) и стабильность, и вы готовы пожертвовать дополнительной памятью.
