Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Определение

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

---

Принцип работы алгоритма

Сортировка слиянием работает следующим образом:

1. Разделяем массив на подмассивы, состоящие из одного элемента.
2. Попарно объединяем подмассивы, их сортируя, пока не останется только один подмассив. Это и будет отсортированный исходный массив.

---

Схематическая работа алгоритма

Есть неотсортированная последовательность данных

Первый шаг

Соединяем попарно элементы и сортируем их в порядке возрастания. Если у элемента нет пары, то переносим его отдельно.

Второй шаг

Далее соединяем пары элементов с другой парой элементов и сортируем их.

Третий шаг

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

Четвёртый шаг

Соединяем получившийся массив с оставшимся элементом и сортируем.

---

Вычислительная сложность

Время работы сортировки слиянием - $O(n * log_{2} n)$.

---

Псевдокод

Аннотация:
i - индеск элемента первой половины массива
j - индеск элемента второй половины массива

массив <- исходный массив

функция разделить_массив_пополам(массив):
    середина <- длина массива / 2
    
    если длина массива > 1:
        вернуть [массив[:середина], массив[середина:]]]
    иначе:
        вернуть массив

функция разбить_массив(массив):
    если длина массива == 1:
        вернуть [массив]
    иначе:
        первая_половина, вторая_половина <- разделить_массив_пополам(массив)
        
        вернуть разбить_массив(первая_половина) + разбить_массив(вторая_половина)

функция отсортировать_массивы(массивы):
    первый_массив, второй_массив <- массивы
    i, j <- 0
    новый_массив <- пустой массив

    пока i < длина первого_массива и j < длина второго_массива:
        если первый_массив[i] < второй_массив[j]:
            новый_массив.добавить(первый_массив[i])
            i += 1
        иначе:
            новый_массив.добавить(второй_массив[j])
            j += 1
            
        если i < длина первого_массива:
            новый_массив += первый_массив[i:длина первого_массива]

        если j < длина второго_массива:
            новый_массив += второй_массив[j:длина второго_массива]

    вернуть новый_массив

функция объединить(массив):
    конечный_массив <- пустой массив
    если длина массива нечетная:
        массив.добавить(пустой массив)

    для i от 0 до длины массива - 1 с шагом 2:
        текущий <- отсортировать_массивы([массив[i], массив[i + 1]])
        конечный_массив.добавить(текущий)
        
        если длина конечного_массива == 1:
            вернуть конечный_массив[0]

    иначе:
        вернуть объединить(конечный_массив)

функция сортировка_слиянием(массив):
    массив <- разбить_массив(массив)

    вернуть объединить(массив)

---

Реализация на Python

Аннотация:
array_in_half - функция разделения массива пополам
array - неотсортированный массив
middle - середина массива
split_array - функция делит массив на подмассивы из одного элемента
first - первая половина массива
second - вторая половина массива
sort_arrays - функция сортирует два подмассива и объединяет их в один
arrays - массив в котором будут храниться два подмассива при сортировке
i - индеск элемента первой половины массива
j - индеск элемента второй половины массива
new_array - подмассив куда будут добавляться отсортированные элементы
merge - функция сортирует и объединяет все подмассивы
final_array - массив, в котором будет создаваться финальный отсортированный массив
curr - отсортированный в функции sort_arrays подмассив
merge_sort - функция сортировки слиянием

def array_in_half(array):  
    if len(array) > 1:  
        middle = len(array) // 2  
        return [array[:middle], array[middle:]]  
        
    return array  
  
def split_array(array):  
    if len(array) == 1:  
        return [array]  
        
    first, second = array_in_half(array)  
    
    return split_array(first) + split_array(second)  
  

def sort_arrays(arrays):  
    first, second = arrays  
    i = j = 0  
    new_array = list()  
    
    while i < len(first) and j < len(second): 
        if first[i] < second[j]:  
            new_array.append(first[i])  
            i += 1  
        else:  
            new_array.append(second[j])  
            j += 1  
               
    if i < len(first) or j < len(second):  
        new_array += first[i:len(first)]  
        new_array += second[j:len(second)] 
         
    return new_array  
  
def merge(array):  
    final_array = list()  
    
    if len(array) % 2 > 0:  
        array.append([])  
        
    for i in range(0, len(array)-1, 2):  
        curr = sort_arrays([array[i], array[i + 1]])  
        final_array.append(curr)  
        
    if len(final_array) == 1:  
        return final_array[0]  
        
    return merge(final_array)  
  
  
def merge_sort(array):  
    array = split_array(array)  
    
    return merge(array)

---

Олимпиадная реализация на C++

Аннотация:
typedef vi - переопределение вектора, содержащего INT
typedef vvi - переопределение вектора, в котором будут храниться подмассивы
split_arr - функция разделения массива на подмассивы из одного элемента
sing_arr - массив для подмассива каждого элемента сортировки
sort_arr - функция сортировки двух массивов и объединения их в один
first - первый подмассив
second - второй подмассив
i,j - индексы подмассивов
merge - функция сортировки и объединения всех подмассивов
final_arr - уже отсортированный массив
curr - отдельный элемент, с которым функция работает

typedef vector<int> vi;
typedef vector<vector<int>> vvi;

vi split_arr(vi &arr) {
  vvi sing_arr;

  for (int i : arr) {
    sing_arr.push_back({i});
  }

  return sing_arr;
}

vi sort_arr(vi &array_1, vi &array_2) {
  vi first = arr1;
  vi second = arr2;
  int i = 0;
  int j = 0;

  vi new_arr;
  while (i < first.size() and j < second.size()) {
    if (first[i] < second[j]) {
      new_arr.push_back(first[i]);
      i++;
    }

    else {
      new_arr.push_back(second[j]);
      j++;
    }
  }

  if (i < first.size() or j < second.size()) {
    new_arr.insert(new_arr.end(), first.begin() + i, first.end());
    new_arr.insert(new_arr.end(), second.begin() + j, second.end());
  }

  return new_arr;
}

vi merge(vvi &arr) {
  vvi final_arr;
  if (arr.size() % 2 > 0) {
    arr.push_back({});
  }

  for (int i = 0; i < arr.size() - 1; i += 2) {
    vi curr = sort_arr(arr[i], arr[i + 1]);
    final_arr.push_back(curr);
  }

  if (final_arr.size() == 1) {
    return final_arr[0];
  }

---

Продуктовая реализация на C++

Аннотация:
template - шаблон функции
typename T - шаблонный тип данных параметра
split_array - функция, которая разбивает исходный массив на массивы, состоящие из одного элемента
array - исходный массив
single array - массив, в котором находятся подмассивы из одного элемента
data - элемент исходного массива
sort_array - функция сортировки двух подмассивов и объединения их в один
array_1 - первый подмассив
array_2 - второй подмассив
first - копия первого подмассива 
second - копия второго подмассива
i, j - индексы первого и второго подмассивов
new_array - Новый объединенный массив
merge - функция сортировки и объединения всех подмассивов
final_array - Уже отсортированный массив
curr - отдельный элемент, с которым работает функция
merge_sort - функция сортировки слиянием

template <typename T>
std::vector<std::vector<T>> split_array(std::vector<T>& array) {
  std::vector<std::vector<T>> single_array;

  for (T data : array) {
    single_array.push_back({data});
  }

  return single_array;
}

template <typename T>
std::vector<T> sort_arrays(std::vector<T>& array_1, std::vector<T>& array_2) {
  std::vector<T> first = array_1;
  std::vector<T> second = array_2;
  int i = 0;
  int j = 0;

  std::vector<T> new_array;
  while (i < first.size() and j < second.size()) {
    if (first[i] < second[j]) {
      new_array.push_back(first[i]);
      i++;
    }

    else {
      new_array.push_back(second[j]);
      j++;
    }
  }

  if (i < first.size() or j < second.size()) {
    new_array.insert(new_array.end(), first.begin() + i, first.end());
    new_array.insert(new_array.end(), second.begin() + j, second.end());
  }
  return new_array;
}

template <typename T>
std::vector<T> merge(std::vector<std::vector<T>>& array) {
  std::vector<std::vector<T>> final_array;

  if (array.size() % 2 > 0) {
    array.push_back({});
  }

  for (int i = 0; i < array.size() - 1; i += 2) {
    std::vector<T> curr = sort_arrays(array[i], array[i + 1]);
    final_array.push_back(curr);
  }

  if (final_array.size() == 1) {
    return final_array[0];
  }

  return merge(final_array);
}

template <typename T>
std::vector<T> merge_sort(std::vector<T>& array) {
  std::vector<std::vector<T>> single_array = split_array(array);
  return merge(single_array);
}