Определение

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

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

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

1. Разделяем массив на подмассивы, состоящие из одного элемента.

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

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

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

Первый шаг

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

Второй шаг

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

Третий шаг

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

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

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

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

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

Псевдокод

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

Функция разделить_пополам(массив)  
    Если длина массива больше 1  
        середина = длина массива // 2  
        Вернуть [массив[:середина], массив[середина:]]  
    Иначе  
        Вернуть массив  
  
Функция разделить_массив(массив)  
    Если длина массива равна 1  
        Вернуть [массив]  
    Иначе  
        первая_половина, вторая_половина = разделить_пополам(массив)  
        Вернуть разделить_массив(первая_половина) + разделить_массив(вторая_половина)  
  
Функция сортировать_массивы(массивы)  
    первая_половина, вторая_половина = массивы  
    i = j = 0  
    новый_массив = пустой список  
    Пока i < длина первой_половины и j < длина второй_половины  
        Если первая_половина[i] < вторая_половина[j]  
            добавить первая_половина[i] в новый_массив  
            i += 1  
        Иначе  
            добавить вторая_половина[j] в новый_массив  
            j += 1  
    Если i < длина первой_половины или j < длина второй_половины  
        добавить оставшиеся элементы первой_половины[i:длина первой_половины] в новый_массив  
        добавить оставшиеся элементы второй_половины[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_array - функция разделения массива на подмассивы из одного элемента  
sing_arr - массив для подмассива каждого элемента сортировки  
sort_arrays - функция сортировки двух массивов и объединения их в один  
first - первый подмассив  
second - второй подмассив  
i,j - индексы подмассивов  
merge - функция сортировки и объединения всех подмассивов  
final_array - уже отсортированный массив  
curr - отдельный элемент, с которым функция работает  
merge_sort - функция сортировки слиянием

typedef vector<int> vi;  
typedef vector<vector<int>> vvi;  
  
vi split_array(vi &arr) {  
  vvi sing_arr;  
  
  for (int i : arr) {  
    sing_arr.push_back({i});  
  }  
  
  return sing_arr;  
}  
  
vi sort_arrays(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_arrays(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);  
}