Алгоритм сортировки слиянием: объяснение в JavaScript

Сортировка слиянием - один из наиболее часто используемых алгоритмов сортировки в информатике, а также один из самых эффективных. Он основан на принципе «разделяй и властвуй», и этот метод является основой эффективных алгоритмов для множества различных проблем.

В этой статье я расскажу о концепции, лежащей в основе этого алгоритма, и покажу вам пример на JavaScript.

Объясняя концепцию

Алгоритм «разделяй и властвуй» рекурсивно разбивает проблему на более мелкие, пока они не станут достаточно простыми для решения. Затем решения подзадач объединяются, чтобы получить решение исходной проблемы.

Идея алгоритма сортировки заключается в том, что легче отсортировать два отсортированных массива, чем один несортированный. Когда у вас есть два отсортированных массива, вы можете объединить их в один массив, сравнивая их элементы один за другим и добавляя сначала меньший элемент.

Концепцию довольно легко понять, но все же остается один вопрос. Как достичь состояния, в котором у нас есть два отсортированных массива? Что ж, мы можем добиться этого с помощью Divide and Conquer. Мы собираемся рекурсивно разделить массив пополам. Мы делаем это до тех пор, пока не достигнем точки, в которой мы сравниваем несколько пар массивов с одним элементом.

Ниже вы можете увидеть, как мы рекурсивно разбиваем массив на более мелкие массивы, пока не получим только массивы из отдельных элементов.

                        [1,9,3,8,6,5,7,4,2]
                 [1,9,3,8]              [6,5,7,4,2]    
             [1,9]       [3,8]       [6,5]       [7,4,2]  
           [1]   [9]   [3]   [8]   [6]   [5]   [7]     [4,2]  
           [1]   [9]   [3]   [8]   [6]   [5]   [7]   [4]   [2]

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

          [1]   [9]   [3]   [8]   [6]   [5]   [7]   [4]   [2]
          [1]   [9]   [3]   [8]   [6]   [5]   [7]     [2,4]
            [1,9]       [3,8]       [5,6]       [2,4,7]
                [1,3,8,9]              [2,4,5,6,7]
                      [1,2,3,4,5,6,7,8,9]

Ниже вы увидите реализацию на JavaScript. Он использует встроенную функцию среза, чтобы получить нужные нам части массива. В этом коде мы используем две отдельные функции, чтобы наглядно показать, как работает процесс.

const mergeSort = (arr) => {
  if (arr.length <= 1) {
    return arr;
  }
  const middle = Math.floor(arr.length / 2);
  return mergeArray(
    mergeSort(arr.slice(0, middle)), 
    mergeSort(arr.slice(middle))
  );
};
const mergeArray = (left, right) => {
  let result = [];
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  return [...result, ...left, ...right];
};
const unorderedArray = [1, 9, 3, 8, 6, 5, 7, 4, 2];
console.log(mergeSort(unorderedArray)); // Returns ordered array

Функция mergeSort разбивает массив и снова вызывает себя с каждой половиной. На обратном пути мы используем mergeArray, чтобы собрать массивы с элементами в правильном порядке.

Как видно из кода, реализация алгоритма сортировки слиянием довольно проста. Как только вы поймете концепцию, ее относительно легко реализовать на любом языке.

Ну вот и все. Дайте мне знать, что вы думаете. Удачного кодирования!

Больше контента на plainenglish.io