Сортировка слиянием (Merge Sort)

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

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

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

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

Псевдокод

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

``` 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]` с использованием сортировки слиянием:

1. Разделение массива до тех пор, пока не получим списки из одного элемента: `[38] [27] [43] [3] [9] [82] [10]`
2. Слияние списков:
   1. `[27, 38]`
   2. `[3, 43]`
   3. `[9, 82]`
   4. `[10]`
3. Слияние списков:
   1. `[3, 27, 38, 43]`
   2. `[9, 10, 82]`
4. Слияние списков:
   1. `[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)$.
• Стабильная сортировка.
• Хорошо подходит для сортировки связных списков.

Недостатки:

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

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

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