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

Алгоритм

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

Код

Слияние

Функция начинает с нулевых элементов обоих массивов, сравнивает их и находит минимальный. Для того массива, в котором нашелся минимум, активный индекс сдвигается вправо. Сравнения происходят пока один из массивов не закончится, тогда остаток другого просто присоединяется к результирующему массиву.

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()) 
    } 
  } 
  
  return [ ...arr, ...left, ...right ] 
}

Сортировка

Делит массив на две части, затем отправляет каждую часть на рекурсивную сортировку, а затем снова объединяет их с помощью функции merge.

function mergeSort(array) { 
  const half = array.length / 2
  
  if(array.length < 2) { 
    return array 
  } 
  
  const left = array.splice(0, half) 
  
  return merge(mergeSort(left),mergeSort(array)) 
}