Вступление

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

Как правило, легче найти элемент (называемый ключом) в данном списке, если список отсортирован как визуально, так и алгоритмически.

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

В этой статье мы увидим логику сортировки слиянием, реализуем ее на JavaScript и визуализируем в действии. Наконец, мы сравним сортировку слиянием с другими алгоритмами с точки зрения пространственной и временной сложности.

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

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

Вот шаги, которые выполняет Сортировка слиянием:

1. Разделите данный список на две половины (примерно равные половины в случае списка с нечетным числом элементов).
2. Продолжайте разделять подмассивы таким же образом, пока не останетесь только с массивами с одним элементом.
3. Начиная с массивов с одним элементом, объедините подмассивы, чтобы отсортировать каждый объединенный подмассив.
4. Повторите шаг 3 с одним отсортированным массивом.

Давайте посмотрим, как сортировка слиянием работает с таким массивом, как [4, 8, 7, 2, 11, 1, 3] :

{.ezlazyload}

Реализация сортировки слиянием в JavaScript

Давайте сначала напишем код для merge() двух отсортированных подмассивов в отсортированный массив. Очень важно помнить, что оба подмассива уже отсортированы, и мы просто merge() .

Мы можем сделать это, пройдя по обоим этим подмассивам и добавив один за другим элементы, чтобы полученный массив также был отсортирован:

 function merge(left, right) { 
 let arr = [] 
 // Break out of loop if any one of the array gets empty 
 while (left.length && right.length) { 
 // Pick the smaller among the smallest element of left and right sub arrays 
 if (left[0] < right[0]) { 
 arr.push(left.shift()) 
 } else { 
 arr.push(right.shift()) 
 } 
 } 
 
 // Concatenating the leftover elements 
 // (in case we didn't go through the entire left or right array) 
 return [ ...arr, ...left, ...right ] 
 } 

В этой функции мы берем два отсортированных подмассива ( left , right ) и объединяем их, чтобы получить один отсортированный массив. Сначала мы создаем пустой массив. Позже мы выбираем меньший из самых маленьких неотобранных элементов в left и right подмассивах и помещаем их в пустой массив. Нам нужно проверить только первые элементы в left и right подмассивах, поскольку они оба отсортированы.

При этом мы удаляем выбранный элемент из подмассива (это достигается с помощью функции shift() ). Продолжаем этот процесс, пока один из подмассивов не станет пустым. После этого мы помещаем оставшиеся элементы непустого подмассива (потому что они уже отсортированы) в основной массив.

Как мы теперь имеем код для слияния двух отсортированных массивов (властвуй часть разделяй и властвуй), выпишем окончательный код для алгоритма сортировки слиянием. Это означает, что нам нужно продолжать разбивать массивы, пока мы не получим массивы, содержащие только один элемент:

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

Здесь мы определяем среднюю точку и разделяем массив на два подмассива с помощью функции splice() . При нечетном количестве элементов левый получает меньшее количество элементов. Мы делим до тех пор, пока не останемся с одноэлементными массивами ( array.length < 2 ). После этого мы начинаем объединять подмассивы с помощью написанной ранее функции merge() .

Теперь, когда у нас есть код, давайте посмотрим на результат выполнения функции из нашего предыдущего примера:

 array = [4, 8, 7, 2, 11, 1, 3]; 
 console.log(mergeSort(array)); 

Это дает нам ожидаемый результат:

 1,2,3,4,7,8,11 

Эффективность сортировки слиянием

Наихудшая временная сложность сортировки слиянием равна O (nlogn) , такая же, как и для лучшей временной сложности для быстрой сортировки . Что касается скорости, сортировка слиянием - один из самых быстрых алгоритмов сортировки.

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

Еще одним преимуществом сортировки слиянием является то, что она очень хорошо подходит для многопоточности, поскольку каждая соответствующая половина и сортируется отдельно. Другой распространенный способ сократить время выполнения сортировки слиянием - остановиться, когда мы дойдем до относительно небольших подмассивов (~ 7), и использовать сортировку вставкой для их сортировки.

Это сделано потому, что сортировка вставкой очень хорошо работает с небольшими или почти отсортированными массивами. Намного лучше, чем его более глобально эффективные аналоги.

Заключение

В этой статье мы увидели логику алгоритма сортировки слиянием, как реализовать его в JavaScript, и узнали о его производительности. Это один из основных алгоритмов сортировки, который действительно полезен для наглядного примера стратегии «разделяй и властвуй».