Сортировка слиянием на Java — пошаговая реализация с разбором

Сортировка слиянием (Merge Sort) — ещё один классический алгоритм, построенный на принципе «разделяй и властвуй». Его придумал Джон фон Нейман в 1945 году. В отличие от быстрой сортировки, сортировка слиянием всегда работает за O(n log n) — даже в худшем случае. Это её главное преимущество.

Идея алгоритма:

1. Делим массив пополам на две примерно равные части.

2. Рекурсивно сортируем левую половину.

3. Рекурсивно сортируем правую половину.

4. Сливаем две отсортированные половины в один отсортированный массив. Это делается за один проход: сравниваем первые элементы обеих половин и берём меньший.

5. Деление идёт, пока подмассив не станет размером 1 элемент — такой массив уже отсортирован сам по себе.

Примечание

Асимптотическая сложность:

• Время (всегда): O(n log n) — стабильно во всех случаях.

• Память: O(n) — нужны временные массивы для слияния.

• Стабильность: алгоритм сохраняет порядок одинаковых элементов (это важно при сортировке объектов по нескольким полям).

Совет

Сортировка слиянием хороша, когда нужна стабильность или гарантированная производительность. В Java метод Arrays.sort() для массивов объектов использует TimSort — гибрид сортировки слиянием и вставками.

Чтобы понять этот пример, нужно знать следующие темы Java: методы Java, цикл while и do…while в Java, массивы в Java.

Сортировка слиянием на Java

Алгоритм сортировки слиянием основан на принципе «разделяй и властвуй», где задача делится на несколько подзадач. Каждая подзадача решается отдельно, и в конце результаты объединяются, образуя окончательное решение.

Пример: программа на Java для реализации сортировки слиянием

import java.util.Arrays;

// Merge sort in Java

class Main {

  // Merge two sub arrays L and M into array
  void merge(int array[], int p, int q, int r) {

    int n1 = q - p + 1;
    int n2 = r - q;

    int L[] = new int[n1];
    int M[] = new int[n2];

    // fill the left and right array
    for (int i = 0; i < n1; i++)
      L[i] = array[p + i];
    for (int j = 0; j < n2; j++)
      M[j] = array[q + 1 + j];

    // Maintain current index of sub-arrays and main array
    int i, j, k;
    i = 0;
    j = 0;
    k = p;

    // Until we reach either end of either L or M, pick larger among
    // elements L and M and place them in the correct position at A[p..r]
    // for sorting in descending
    // use if(L[i] >= <[j])
    while (i < n1 && j < n2) {
      if (L[i] <= M[j]) {
        array[k] = L[i];
        i++;
      } else {
        array[k] = M[j];
        j++;
      }
      k++;
    }

    // When we run out of elements in either L or M,
    // pick up the remaining elements and put in A[p..r]
    while (i < n1) {
      array[k] = L[i];
      i++;
      k++;
    }

    while (j < n2) {
      array[k] = M[j];
      j++;
      k++;
    }
  }

  // Divide the array into two sub arrays, sort them and merge them
  void mergeSort(int array[], int left, int right) {
    if (left < right) {

      // m is the point where the array is divided into two sub arrays
      int mid = (left + right) / 2;

      // recursive call to each sub arrays
      mergeSort(array, left, mid);
      mergeSort(array, mid + 1, right);

      // Merge the sorted sub arrays
      merge(array, left, mid, right);
    }
  }

  public static void main(String args[]) {

    // created an unsorted array
    int[] array = { 6, 5, 12, 10, 9, 1 };

    Main ob = new Main();

    // call the method mergeSort()
    // pass argument: array, first index and last index
    ob.mergeSort(array, 0, array.length - 1);

    System.out.println("Sorted Array:");
    System.out.println(Arrays.toString(array));
  }
}

Вывод:

Sorted Array:
[1, 5, 6, 9, 10, 12]

Здесь элементы массива отсортированы по возрастанию. Если мы хотим отсортировать элементы по убыванию, то внутри первого цикла while метода merge() нужно изменить код так:

// the less than sign is changed to greater than
if (L[i] >= M[j]) {

Важно

Главная операция Merge Sort — слияние двух отсортированных массивов в один за линейное время O(n). Именно за счёт того, что каждое слияние занимает O(n), а уровней деления — log n, итоговая сложность получается O(n log n).