Структуры данных — алгоритм сортировки слиянием

Сортировка слиянием — это метод сортировки, основанный на технике «разделяй и властвуй». Учитывая сложность времени в худшем случае Ο (n log n), это один из наиболее уважаемых алгоритмов.

Сортировка слиянием сначала делит массив на равные половины, а затем объединяет их отсортированным образом.

Как работает сортировка слиянием?

Чтобы понять сортировку слиянием, мы берем несортированный массив следующим образом:

Мы знаем, что сортировка слиянием сначала делит весь массив итеративно на равные половины, если не достигнуты атомарные значения. Здесь мы видим, что массив из 8 элементов делится на два массива размером 4.

Это не меняет последовательности появления предметов в оригинале. Теперь мы разделим эти два массива пополам.

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

Теперь мы объединяем их точно так же, как они были разбиты. Обратите внимание на коды цветов, приведенные в этих списках.

Сначала мы сравниваем элемент для каждого списка, а затем сортируем их в другой список. Мы видим, что 14 и 33 находятся в отсортированных позициях. Мы сравниваем 27 и 10 и в целевом списке из 2 значений сначала ставим 10, а затем 27. Мы меняем порядок 19 и 35, тогда как 42 и 44 располагаются последовательно.

На следующей итерации фазы объединения мы сравниваем списки двух значений данных и объединяем их в список найденных значений данных, размещая все в отсортированном порядке.

После окончательного объединения список должен выглядеть так:

Теперь мы должны изучить некоторые программные аспекты сортировки слиянием.

Алгоритм

Сортировка слиянием продолжает делить список на равные половины, пока он больше не может быть разделен. По определению, если это только один элемент в списке, он сортируется. Затем сортировка слиянием объединяет отсортированные списки меньшего размера, сохраняя сортировку нового списка.

Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.

ПСЕВДОКОД

Теперь мы увидим псевдокоды для функций сортировки слиянием. Поскольку наши алгоритмы указывают на две основные функции — разделяй и объединяй.

Сортировка слиянием работает с рекурсией, и мы увидим нашу реализацию таким же образом.

procedure mergesort( var a as array )
   if ( n == 1 ) return a

   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]

   l1 = mergesort( l1 )
   l2 = mergesort( l2 )

   return merge( l1, l2 )
end procedure

procedure merge( var a as array, var b as array )

   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while
   
   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while
   
   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while
   
   return c
	
end procedure

Чтобы узнать о реализации сортировки слиянием на языке программирования C, пожалуйста, нажмите здесь .