Алгоритм сортировки-слияния

Сортировка слиянием представляет собой алгоритм сортировки  который состоит из объединения двух списков, отсортированных в один. Его принцип основан на методе deviser pour régner. Преимущество sort-to-merge заключается в том, что два списка объединяются одновременно, поэтому мы можем сделать реализацию с помощью threads.

Алгоритм известен своей эффективностью в сложности (время и память) и сортировкой списков:
  • Мы разрезаем данные на две равные части.
  • Мы сортируем данные каждого part (мы разделяем каждую часть, алгоритм становится рекурсивным).
  • Мы объединяем две части.
Мы рекурсивно разделяем начальный массив на два подмассива, пока массив не будет содержать только один элемент. После того, как элементы отсортированы независимо друг от друга, с этого момента backtracking и мы собираемся объединить подтаблицы до тех пор, пока не получите отсортированную стартовую доску. Слияние состоит из последовательных сравнений.

Пример

Предположим, мы хотим отсортировать следующую таблицу: [ 38, 27 ,43, 3, 9, 82, 10]

Сортировка Fusion в Java

Algorithm


TriFusion ALGORITHM(T, слева, справа);
    Т: таблица значений;
    left,right: целое число;
    center: целое число;
НАВЕРХ   
    IF (слева < справа) THEN
          ← по центру (слева + справа) / 2;
          TriFusion (Т, слева, в центре);
          TriFusion (Т, центр + 1, справа);
          MERGE(T, влево, по центру, вправо);
    FSI
FIN.