Сортировка слиянием - это эффективный алгоритм сортировки, который основан на разделении и слиянии. Он использует принцип "разделяй и властвуй", при котором массив разбивается на две половины, каждая из которых сортируется рекурсивно. Затем отсортированные половины сливаются в один отсортированный массив. Ниже представлена реализация сортировки слиянием на языке Java с использованием логической парадигмы:

java

public class MergeSort {



    public static void main(String[] args) {

        int[] array = {5, 2, 8, 6, 1, 9, 4};

        mergeSort(array); // вызываем метод сортировки слиянием

        for (int i : array) {

            System.out.print(i + " ");

        }

    }



    public static void mergeSort(int[] array) {

        if (array.length < 2) {

            return; // базовый случай: если массив состоит из одного элемента или пустой, то он уже отсортирован

        }



        // Разделение массива на две половины

        int mid = array.length / 2;

        int[] leftArray = new int[mid];

        int[] rightArray = new int[array.length - mid];



        for (int i = 0; i < mid; i++) {

            leftArray[i] = array[i];

        }



        for (int i = mid; i < array.length; i++) {

            rightArray[i - mid] = array[i];

        }



        // Рекурсивная сортировка обеих половинок массива

        mergeSort(leftArray);

        mergeSort(rightArray);



        // Слияние отсортированных половинок

        merge(leftArray, rightArray, array);

    }



    public static void merge(int[] leftArray, int[] rightArray, int[] resultArray) {

        int i = 0;

        int j = 0;

        int k = 0;



        // Последовательное сравнение элементов обеих половинок и запись минимального элемента в результирующий массив

        while (i < leftArray.length && j < rightArray.length) {

            if (leftArray[i] <= rightArray[j]) {

                resultArray[k] = leftArray[i];

                i++;

            } else {

                resultArray[k] = rightArray[j];

                j++;

            }

            k++;

        }



        // Копирование оставшихся элементов из левой половинки (если есть)

        while (i < leftArray.length) {

            resultArray[k] = leftArray[i];

            i++;

            k++;

        }



        // Копирование оставшихся элементов из правой половинки (если есть)

        while (j < rightArray.length) {

            resultArray[k] = rightArray[j];

            j++;

            k++;

        }

    }



}

В данном примере мы объявляем метод `mergeSort`, который принимает массив чисел в качестве аргумента. Внутри метода, если массив состоит из одного элемента или пустой, он сразу возвращает значение (базовый случай). В противном случае, массив разделяется на две половины и каждая половина сортируется рекурсивно. Далее объявляется метод `merge`, который сливает отсортированные половины с помощью сравнения и копирования элементов из левой и правой половинок в результирующий массив. Затем происходит слияние отсортированных половин, и массив с числами будет отсортирован. Метод `main` демонстрирует работу сортировки слиянием, принимая входной массив и вызывая метод `mergeSort`. Затем отсортированный массив выводится на экран. Сортировка слиянием имеет временную сложность O(n log n), что делает ее очень эффективным алгоритмом сортировки для больших массивов. Она также является стабильной, то есть сохраняет относительный порядок равных элементов.