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

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

Одна из самых стабильных сортировок

Часто в разработке есть задача отсортировать данные за один проход или даже по мере их появления. Классическое решение — использовать быструю сортировку, то есть сортировку вокруг опорного элемента. Но если неверно выбрать этот опорный элемент, скорость сортировки резко возрастёт. А нам это не нужно. 

Чтобы не столкнуться с этой проблемой, используют сортировку слиянием.

В чём идея сортировки слиянием

Основной принцип сортировки слиянием такой: делим массив пополам, каждый из них сортируем слиянием и потом соединяем оба массива. Каждый разделённый массив тоже нарезаем на два подмассива до тех пор, пока в каждом не окажется по одному элементу.

Здесь тоже используется рекурсия — то есть повторение алгоритма внутри самого алгоритма. Но это только один из элементов алгоритма.

Второй элемент — соединение отсортированных элементов между собой, причём тоже хитрым способом: раз оба массива уже отсортированы, то нам достаточно сравнивать элементы друг с другом по очереди и заносить в итоговый массив данные по порядку. 

Если представить алгоритм по шагам, он будет выглядеть так:

  1. Исходный массив: [4 2 5 1].
  2. Делим пополам: [4 2] ←→ [5 1] (у нас появилось два новых массива, значит, к ним применяем тоже сортировку слиянием).
  3. Делим пополам первый массив: [4] ←→ [2].
  4. Раз в каждом по одному элементу, то сортируем и склеиваем в один: [2 4].
  5. Делим пополам второй массив: [5] ←→ [1].
  6. Раз в каждом по одному элементу — сортируем и склеиваем в один: [1 5].
  7. К нам вернулись два отсортированных подмассива, а значит, нам нужно их отсортировать и склеить в один. 
  8. Сравниваем первые элементы: 1 и 2. Единица меньше двух, значит, в итоговый массив записываем 1, и у нас остаются два массива: [2 4] и [5].
  9. Сравниваем первые элементы: 2 и 5. Двойка меньше пяти, значит, в итоговый массив записываем 2, и у нас остаются два массива: [4] и [5].
  10. Точно так же сравниваем первые элементы до тех пор, пока в обоих массивах не исчезнут все элементы. Как только это произойдёт — массив отсортирован.

Если проще воспринимать работу алгоритма в виде картинок — держите анимацию сортировки слиянием:

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

Особенность алгоритма

Главное преимущество сортировки слиянием — она работает всегда с одной и той же скоростью на любых массивах. Допустим, у нас есть два массива:

  1. В одном будут числа в случайном порядке.
  2. В другом — уже отсортированные числа, но последний и предпоследний элементы (разные) просто поменяны местами.

В обоих случаях сортировка слиянием покажет одно и то же время: ей всё равно, какие данные обрабатывать, алгоритм всё равно сделает это за один проход и одинаковое время. Благодаря этому свойству алгоритм используют там, где нужно обработать данные за заранее известное время. Например, если для сортировки 1000 элементов серверу требуется 50 миллисекунд, то можно настроить ему отправку новой партии данных каждую 51 миллисекунду — так мы будем уверены, что к моменту отправки новых данных старые уже будут обработаны.

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

Запустите этот код в браузере, чтобы посмотреть, на какие части алгоритм делит входной массив и как он обрабатывает их по очереди. Обратите внимание на три точки в команде return — они означают, что эта переменная может быть, а может и не быть в итоговом результате. Про то, как работают эти три точки и зачем они нужны, расскажем в отдельной статье, а пока читайте комментарии и проверяйте код в деле:

// слияние массивов с одновременной сортировкой
// на вход подаются уже отсортированные левая и правая части 
function merge(left, right) {
    // сюда будем складывать результат
    let arr = []
    // пока в каждой части есть хотя бы один элемент — выполняем цикл
    while (left.length && right.length) {
        // смотрим на наименьший элемент из тех, что стоят в начале обоих массивов
        if (left[0] < right[0]) {
            // если слева был элемент меньше —
            // забираем его оттуда и отправляем в массив с результатом
            arr.push(left.shift())  
        } else {
            // в противном случае забираем элемент из правой части
            arr.push(right.shift()) 
        }
    }
    // выводим результат слияния отсортированных массивов
    console.log('Результат: ' + arr);

    // возвращаем отсортированный массив и добавляем к нему в конец отсортированный остаток от какой-либо части, если её так и не обработали в цикле
    return [ ...arr, ...left, ...right ]
}

// делим массивы пополам до тех пор, пока в них не останется элементов
function mergeSort(array) {
  // находим середину 
  const half = array.length / 2
  
  // если в нашем массиве и так меньше двух элементов — возвращаем его
  if(array.length < 2){
    return array 
  }
  
  // делим массив на две части и левую отправляем в новый массив
  const left = array.splice(0, half)
  // выводим промежуточный результат
  console.log('Слева:' + left);
  console.log('Справа:' + array);
  // запускаем рекурсию и отдаём ей правую и левую части массива
  return merge(mergeSort(left),mergeSort(array))
}

// исходный массив
array = [3, 5, 1, 6, 9, 8, 2];
console.log(mergeSort(array));

Текст:

Михаил Полянин

Редактор:

Максим Ильяхов

Художник:

Алексей Сухов

Корректор:

Ирина Михеева

Вёрстка:

Кирилл Климентьев

Соцсети:

Виталий Вебер

Это айти. Вот как сюда войти
Если вам близко то, о чём написано выше, у вас есть все шансы стать разработчиком, тестировщиком, дата-сайентистом или менеджером в сфере ИТ. Тут хорошо платят и приятная компания. Стоит хотя бы изучить вопрос.
Изучить вопрос
Это айти. Вот как сюда войти Это айти. Вот как сюда войти Это айти. Вот как сюда войти Это айти. Вот как сюда войти
Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Еще по теме
Как начать программировать с нуля

Подборка материалов для начинающих.

easy
Как работает беспроводная зарядка
Как работает беспроводная зарядка

Всё дело в магнитном поле.

easy
Как выглядит сервер
Как выглядит сервер

Он может быть размером со шкаф или со спичечный коробок

easy
Программист учит компьютер играть в Тетрис
Программист учит компьютер играть в Тетрис

А он легко бьет мировой рекорд.

hard
Как устроен и зачем нужен квантовый компьютер

Это прорыв в технологиях или очередной биткоин?

medium
Почему в Windows нельзя создать папку или файл с именем Con
Почему в Windows нельзя создать папку или файл с именем Con

Всё дело в обратной совместимости

easy
Разбор: непобедимый алгоритм для игры «4 в ряд»
Разбор: непобедимый алгоритм для игры «4 в ряд»

Разбор видео Code Bullet про трюки в оптимизации алгоритмов

medium
Кто такой мидл и как им стать

Если вы это читаете, у вас больше шансов, чем у остальных.

easy
Почему программистам сложно работать со временем в программах
Почему программистам сложно работать со временем в программах

Потому что иногда появляется время 23:59:60

medium
Что такое UNIX и зачем он нужен
Что такое UNIX и зачем он нужен

Операционная система, которая изменила мир, хотя в ней почти никто не работал

medium
medium