Алгоритм сортировки слиянием был изобретен Джоном фон Нейманом в 1945 году. Это эффективный алгоритм, используется подход разделяй и властвуй.
- Сортировка слиянием несколько раз делит массив на более мелкие куски, до тех пор, пока мы больше не сможем разделить массив на куски.
- Он повторно объединяет фрагменты массива для получения отсортированного массива.
Пример: [3,4,2,1]
1. Во-первых, мы должны разделить массив на более мелкие куски.
left [ 3 , 4 ] right [ 2, 1 ]
[ 3 ] [ 4 ] [ 2 ] [ 1]
2. Мы должны объединить меньшие куски, чтобы получить сортированный массив. Сравниваем 3 и 4 они уже отсортированы, в следующем 2 и 1 поставить 1первый на место второго.
left [ 3 , 4 ] right [ 2, 1 ]
[ 3 ] [ 4 ] [ 2 ] [ 1]
[3, 4 ] [1 ,2 ]
Теперь сравните индекс левой части 0 и индекс правой части 0, которые являются 3 и 1.
где 1 меньше 3, поэтому мы удаляем 1 из правой части и помещаем в сортированный список.
left [ 3 , 4 ] right [ 1, 2 ]
[ 3] [ 4 ] [ 2 ] [ 1]
[3, 4 ] [ 2 ]
sorted array [ 1 ]
Снова проверяем 3 и 2 и удаляем 2 из правой части и добавляем в сортированный список
left [ 3 , 4 ] right [ 1, 2 ]
[ 3] [ 4 ] [ 2 ] [ 1]
[3, 4 ] [ ]
sorted array [ 1 ,2 ]
Теперь добавьте левую и правую части с отсортированным списком.
left [ 3 , 4 ] right [ 1, 2 ]
[ 3] [ 4 ] [ 2 ] [ 1]
[3, 4 ] [ ]
sorted array [ 1 ,2 ,3, 4]
Давайте реализуем алгоритм сортировки слиянием
function mergeSort(array,half = array.length/2){
if(array.length < 2){
return array // это значит, что мы больше не делим массив
// на более мелкие куски
}
const left = array.splice( 0,half ); //левая часть массива
return merger( mergeSort( left ),mergeSort( array ) ) }
В приведенном выше коде мы используем метод splice, который удаляет левую часть массива, так что оставшаяся часть массива является правой.
Далее нам нужно написать функцию слияния, которая поможет нам объединить левую и правую часть массива и вернет отсортированный список.
function merger(left, right) {
const arr = [ ];
while (left.length && right.length) {
if (left[ 0 ] < right[ 0 ]) {
arr.push( left.shift( ) )
} else {
arr.push( right.shift( ) )
}
}
return [ ...arr, ...left, ...right ];
}
Итого
conlole.log(mergeSort([10, 5, 3, 8, 2, 6, 4, 1, 7, 9])); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]