Что такое сортировка слиянием?
Сортировка слиянием — это метод сортировки, использующий стратегию «разделяй и властвуй».
Проще говоря, он делит заданный массив на две половины, рекурсивно вызывает себя для этих двух половин, а затем объединяет отсортированные половины.
Почему важна сортировка слиянием?
Сортировка слиянием имеет временную сложность в наихудшем, среднем и наилучшем случаях O(n log n). Этоквазилинейное время, в котором используются одни из самых быстрых алгоритмов сравнительной сортировки, включая Quicksort и Heapsort.
Как работает сортировка слиянием?
Мы можем рассмотреть несортированный массив, показанный ниже:
{ 65 24 31 12 6 2 1 19 }
Теперь разделим весь массив на равные половины. Поскольку приведенный выше массив имеет 8 значений, то его можно разделить на два массива по 4 значения в каждом. (Если размер массива нечетный, то не беспокойтесь — последнее значение останется в стороне до процесса сортировки).
{ 65 24 31 12 } { 6 2 1 19 }
Мы снова разделим эти два массива пополам.
{ 65 24 } { 31 12 } { 6 2 } { 1 19 }
Эти массивы теперь снова будут разделены пополам, так что их нельзя будет снова разделить (несет одно значение).
{ 65 } { 24 } { 31 } { 12 } { 6 } { 2 } { 1 } { 19 }
Теперь значения будут объединены в массив так же, как он был разбит. Для этого мы должны сравнить элемент для каждого списка, а затем объединить их в другой список при их сортировке. Принимая во внимание первые два значения, мы видим, что они не в правильном порядке, поэтому мы поменяем их местами, прежде чем назначать их в один массив. Этот процесс будет продолжаться для остальных значений соответственно.
{ 24 65 } { 12 31 } { 2 6 } { 1 19 }
На следующей итерации мы еще раз сравним значения и объединим их в два массива.
{ 12 24 31 65 } { 1 2 6 19 }
Затем идет последняя итерация, которая сравнивает значения и объединяет два массива в один.
{ 1 2 6 12 19 24 31 65 }
Java-реализация алгоритма сортировки слиянием
Поздравляем! Теперь вы изучили основы алгоритма сортировки слиянием!
А пока ставьте лайки этой статье сколько угодно, если она вам понравилась, оставляйте комментарии внизу, если вас что-то беспокоит, проверяйте мой профиль в LinkedIn и подписывайтесь на меня в Medium, чтобы не пропустить еще больше замечательных статей!
