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

Сортировка слиянием делит данный несортированный массив на две равные половины подмассивов, пока n-й (последний) массив не будет содержать единственный элемент. Это основано на том факте, что массив из одного элемента всегда сортируется.

Объединение отсортированных массивов

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

Мы собираемся использовать две функции для реализации этого алгоритма, а именно: функцию mergeSort и функцию слияния. Функция MergeSort будет рекурсивно разделить несортированный массив на n-е подмассивы, как упоминалось выше, в то время как функция слияния будет действовать, как следует из названия, объединяя подмассивы.

Псевдокод функции слияния

  1. Создайте функцию, которая принимает массив.
  2. Создайте три переменные. Один хранит индекс первого массива, другой хранит индекс второго массива, а третий хранит отсортированный массив.
  3. Создайте цикл while, который продолжает работать, если оба индекса первого и второго массива не превышают длину обоих массивов.
  4. Если первый элемент второго массива больше, чем первый, добавьте первый элемент элемента в массив результатов и наоборот.
  5. Создайте цикл while для обоих массивов, который помещает оставшиеся элементы обоих массивов, которые не сравнивались, в массив результатов.
  6. Вернуть массив результатов.

Псевдокод функции MergeSort

  1. Создайте функцию, которая принимает массив.
  2. Создайте базовый вариант, который возвращает подмассив, если в массиве есть один элемент.
  3. Создайте среднюю точку массива и сохраните значение в переменной.
  4. Используйте среднее значение, чтобы разделить массив на левый и правый подмассивы с помощью метода фрагмента массива JavaScript и передать правый и левый массивы в функцию mergeSort и вызвать ее рекурсивно.
  5. Передайте оба массива слева и справа в функцию слияния и верните значение.

Начнем с создания функции слияния.

function merge(arr1, arr2) {
 let i = 0;
 let j = 0;
 let results = [];
 while(i < arr1.length && j < arr2.length) {
  if (arr2[j] > arr1[i]) {
   results.push(arr1[i]);
   i++;  
  }else {
   results.push(arr2[j])
  }
 }
 while(i < arr1.length){
  results.push(arr1[i]);
  i++;
 }
 while(j < arr2.length){
  results.push(arr2[j]);
  j++;
 }
 return results
}

Поскольку теперь у нас есть функция слияния, давайте закончим оставшуюся часть алгоритма, создав нашу функцию сортировки слиянием.

function mergeSort(arr){
 if (arr.length <= 1) return arr;
 
 let mid = Math.floor(arr.length/2);
 let left = mergeSort(arr.slice(0, mid));
 let right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

NB: Этот код и подход можно перенести на любой язык программирования.

Вы можете скопировать код и запустить его в режиме отладки и узнать, что делает каждая строка, пройдя через код. Записывание шагов не спасет вас в будущем, за исключением того, что вы понимаете, как работает код. Удачного кодирования !!!.

Об авторе

Джуд Нвафор - разработчик программного обеспечения @sterling_bank Plc. Вы можете подписаться на меня в твиттере @thaddydore