Сортировка слиянием — это алгоритм разделяй и властвуй. Как следует из названия, этот алгоритм сортировки сочетает в себе две вещи: слияние и сортировку. Здесь он использует тот факт, что массивы длины 0 или 1 всегда сортируются, поэтому мы разбиваем массив на более мелкие массивы из 0 или 1 элементов, а затем строим новый отсортированный массив путем слияния вместе.
Мы разделим алгоритм на двухэтапный. Во-первых, мы создадим вспомогательную функцию под названием merge, которая будет принимать два отсортированных массива в качестве своих параметров и возвращать объединенный + отсортированный массив.
Псевдокод для функции merge()
- Создайте пустой массив, посмотрите на наименьшие значения в каждом входном массиве.
- Хотя есть еще значения, которые мы не рассмотрели
* Если значение в первом массиве меньше, чем значение во втором массиве, вставьте значение из первого массива в наши результаты и перейдите к следующему значению. в первом массиве
* Если значение в первом массиве больше, чем значение во втором массиве, вставьте значение из второго массива в наши результаты и перейдите к следующему значению во втором массиве
* После исчерпания одного массива вставьте все оставшиеся значения из другого массива.
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 }
Во-вторых, для сортировки слиянием мы будем использовать рекурсию.
Псевдокод для сортировки слиянием
- Разбейте массив пополам, пока у вас не будет массивов, которые пусты или имеют один элемент
- Получив отсортированные массивы меньшего размера, объедините эти массивы с другими отсортированными массивами, пока не вернетесь к полной длине массива.
- Как только массив будет снова объединен, верните объединенный + отсортированный массив.
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)