Сортировка слиянием — это алгоритм разделяй и властвуй. Как следует из названия, этот алгоритм сортировки сочетает в себе две вещи: слияние и сортировку. Здесь он использует тот факт, что массивы длины 0 или 1 всегда сортируются, поэтому мы разбиваем массив на более мелкие массивы из 0 или 1 элементов, а затем строим новый отсортированный массив путем слияния вместе.

Мы разделим алгоритм на двухэтапный. Во-первых, мы создадим вспомогательную функцию под названием merge, которая будет принимать два отсортированных массива в качестве своих параметров и возвращать объединенный + отсортированный массив.

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

  1. Создайте пустой массив, посмотрите на наименьшие значения в каждом входном массиве.
  2. Хотя есть еще значения, которые мы не рассмотрели
    * Если значение в первом массиве меньше, чем значение во втором массиве, вставьте значение из первого массива в наши результаты и перейдите к следующему значению. в первом массиве
    * Если значение в первом массиве больше, чем значение во втором массиве, вставьте значение из второго массива в наши результаты и перейдите к следующему значению во втором массиве
    * После исчерпания одного массива вставьте все оставшиеся значения из другого массива.
function merge(arr1, arr2){
    let result = [] 
    let i = 0
    let j = 0
    while(i < arr1.length && j < arr2.length){
        if(arr1[i] > arr2[j]){
            result.push(arr2[j])
            j++
        }else{
            result.push(arr1[i])
            i++
        }
    }
while (i < arr1.length){
        result.push(arr1[i])
        i++
    }
while (j < arr2.length){
        result.push(arr2[j])
        j++
    }
    return result
}

Во-вторых, для сортировки слиянием мы будем использовать рекурсию.

Псевдокод для сортировки слиянием

  1. Разбейте массив пополам, пока у вас не будет массивов, которые пусты или имеют один элемент
  2. Получив отсортированные массивы меньшего размера, объедините эти массивы с другими отсортированными массивами, пока не вернетесь к полной длине массива.
  3. Как только массив будет снова объединен, верните объединенный + отсортированный массив.
function mergeSort(arr){
  if (arr.length <= 1) return arr
    let midPoint = Math.floor(arr.length/2)
    let left = mergeSort(arr.slice(0,midPoint))
    let right = mergeSort(arr.slice(midPoint))
    
    return merge(left, right)
}

Большое О

При сортировке слиянием не имеет значения, отсортированы ли данные, случайны или перевернуты, поскольку у них нет пограничного случая, как в другом алгоритме сортировки. Таким образом, временная сложность сортировки слиянием всегда одинакова для любого случая.
Чтобы разбить анализ временной сложности. Во-первых, временная сложность нашей функции merge() будет большой O длины (arr1 + arr2 ), то есть O(n). Во-вторых, значение функции mergeSort() будет равно O(log n), так как мы каждый раз разбиваем массив пополам. поэтому, объединив их, временная сложность будет O (n log n).

Временная сложность = O(n log n)
Пространственная сложность = O(n)