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

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

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

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

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

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

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

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

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

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

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

В обоих случаях сортировка слиянием покажет одно и то же время: ей всё равно, какие данные обрабатывать, алгоритм всё равно сделает это за один проход и одинаковое время. Благодаря этому свойству алгоритм используют там, где нужно обработать данные за заранее известное время. Например, если для сортировки 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));

Это айти. Вот как сюда войти

Если вам близко то, о чём написано выше, у вас есть все шансы стать разработчиком, тестировщиком, дата-сайентистом или менеджером в сфере ИТ. Тут хорошо платят и приятная компания. Стоит хотя бы изучить вопрос.

Войти бесплатно