Просмотр исходного текста страницы Сортировка слиянием (Merge Sort)

Сортировка слиянием - это эффективный, общий алгоритм сортировки на основе сравнений. Большинство реализаций производят стабильную сортировку, что означает, что порядок равных элементов сохраняется. Сортировка слиянием является алгоритмом "разделяй и властвуй".

== Как это работает ==

Алгоритм сортировки слиянием работает следующим образом:

# '''Разделение''': Разделите несортированный список на n подсписков, каждый из которых содержит один элемент (список из одного элемента считается отсортированным).
# '''Слияние''': Неоднократно сливайте подсписки для создания новых отсортированных подсписков, пока не останется только один подсписок. Это будет отсортированный список.

== Псевдокод ==

Вот псевдокод для алгоритма сортировки слиянием:

```
function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }

    // Разделение массива на две половины
    mid = arr.length / 2;
    left = arr.slice(0, mid);
    right = arr.slice(mid);

    // Рекурсивная сортировка каждой половины
    left = mergeSort(left);
    right = mergeSort(right);

    // Слияние отсортированных половин
    return merge(left, right);
}

function merge(left, right) {
    result = [];
    i = 0;
    j = 0;

    // Слияние элементов из left и right в result
    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));
}
```

== Пример ==

Давайте рассмотрим пример сортировки массива `[38, 27, 43, 3, 9, 82, 10]` с использованием сортировки слиянием:

# Разделение массива до тех пор, пока не получим списки из одного элемента: `[38] [27] [43] [3] [9] [82] [10]`
# Слияние списков:
## `[27, 38]`
## `[3, 43]`
## `[9, 82]`
## `[10]`
# Слияние списков:
## `[3, 27, 38, 43]`
## `[9, 10, 82]`
# Слияние списков:
## `[3, 9, 10, 27, 38, 43, 82]`

== Временная сложность ==

Временная сложность сортировки слиянием всегда $O(n \log n)$, независимо от входных данных.

*   '''Лучший случай''': $O(n \log n)$
*   '''Средний случай''': $O(n \log n)$
*   '''Худший случай''': $O(n \log n)$

== Преимущества и недостатки ==

=== Преимущества: ===

*   Гарантированная временная сложность $O(n \log n)$.
*   Стабильная сортировка.
*   Хорошо подходит для сортировки связных списков.

=== Недостатки: ===

*   Требует дополнительную память для слияния, что может быть недостатком для больших наборов данных.
*   Может быть медленнее, чем быстрая сортировка на практике (из-за накладных расходов на копирование данных).

== Когда использовать ==

Сортировка слиянием является хорошим выбором, когда важна гарантированная производительность и стабильность сортировки. Она также подходит для сортировки больших наборов данных, которые не помещаются в память целиком (внешняя сортировка).