Сортировка слиянием

Сортировка слиянием – отличный пример применения стратегии "разделяй и властвуй".

– Исходный массив разделяется на две примерно равные части.

– Каждая часть сортируется отдельно.

– Обе отсортированные части объединяются в один массив.

Этап 2 выглядит весьма таинственно, ведь он ничего не говорит о том, как именно происходит сортировка частей исходного массива. На самом деле к ним применяется тот же алгоритм (рекурсивное решение задачи). Каждая часть в свою очередь делится на две части, каждая из которых сортируется отдельно, а затем эти части вновь объединяются. Рекурсивное разделение осуществляется до тех пор, пока в каждой части не будет находиться всего один элемент – массив из одного элемента однозначно является отсортированным.

Пример кода:

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

            // середина массива
            let middle = Math.floor(arr.length / 2);

            // два подмассива, которые будут сортироваться отдельно
            let left = arr.slice(0, middle);
            let right = arr.slice(middle);

            // слияние отсортированных подмассивов
            return mergeSortedArrays(mergeSort(left), mergeSort(right));
          }

          function mergeSortedArrays(arr1, arr2) {
            // Результат слияния
            let newArray = [];

            // текущие индексы сравниваемых элементов
            let index1 = 0;
            let index2 = 0;

            // сравнение активных элементов
            while(index1 < arr1.length && index2 < arr2.length) {
              let min = null;
              if (comparator(arr1[index1], arr2[index2]) <= 0) {
                min = arr1[index1]; // добавление минимального элемента в массив
                index1++; // сдвиг индекса активного элемента первого массива
              } else {
                min = arr2[index2];
                index2++;
              }

              newArray.push(min);

            }

            return [...newArray, ...arr1.slice(index1), ...arr2.slice(index2) ];
          }

Основная функция сортировки mergeSort делит массив на две части с помощью метода Array.prototype.slice , отправляет каждую часть на рекурсивную сортировку, а затем снова объединяет их с помощью функции mergeSortedArrays.

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

Сложность

Сортировка слиянием является стабильной. Для нее требуется выполнить n * log(n) операций.

Если у вас возникли трудности с понимаем работы алгоритма, можно посмотреть его визуализацию на видео: