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

В этой статье я расскажу о концепции, лежащей в основе этого алгоритма, и покажу вам пример на 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]

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

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

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

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