Сортировка — фундаментальная операция в информатике, и существуют различные алгоритмы для эффективного выполнения этой задачи. Одним из таких алгоритмов является сортировка слиянием, который следует подходу «разделяй и властвуй». В этой статье мы рассмотрим несколько методов реализации алгоритма сортировки слиянием в PHP, а также приведем примеры кода.

Метод 1: рекурсивная реализация
Рекурсивный подход является наиболее распространенным способом реализации сортировки слиянием. Он предполагает разбиение входного массива на более мелкие подмассивы до тех пор, пока каждый подмассив не будет содержать только один элемент. Затем подмассивы снова объединяются в отсортированном порядке.

function mergeSort(array $arr): array {
    $length = count($arr);
    if ($length <= 1) {
        return $arr;
    }
    $mid = (int) ($length / 2);
    $left = mergeSort(array_slice($arr, 0, $mid));
    $right = mergeSort(array_slice($arr, $mid));
    return merge($left, $right);
}
function merge(array $left, array $right): array {
    $result = [];
    $leftIndex = 0;
    $rightIndex = 0;
    while ($leftIndex < count($left) && $rightIndex < count($right)) {
        if ($left[$leftIndex] < $right[$rightIndex]) {
            $result[] = $left[$leftIndex];
            $leftIndex++;
        } else {
            $result[] = $right[$rightIndex];
            $rightIndex++;
        }
    }
    while ($leftIndex < count($left)) {
        $result[] = $left[$leftIndex];
        $leftIndex++;
    }
    while ($rightIndex < count($right)) {
        $result[] = $right[$rightIndex];
        $rightIndex++;
    }
    return $result;
}

Метод 2: итеративная реализация
Сортировку слиянием также можно реализовать итеративно, используя восходящий подход. Вместо рекурсивного деления массива на подмассивы этот метод начинается с объединения соседних пар элементов и постепенно формируется до полного массива.

function mergeSortIterative(array $arr): array {
    $length = count($arr);
    $subarraySize = 1;
    while ($subarraySize < $length) {
        $left = 0;
        while ($left < ($length - 1)) {
            $mid = min($left + $subarraySize - 1, $length - 1);
            $right = min($left + (2 * $subarraySize) - 1, $length - 1);
            $arr = merge($arr, $left, $mid, $right);
            $left = $left + (2 * $subarraySize);
        }
        $subarraySize *= 2;
    }
    return $arr;
}
function merge(array $arr, int $left, int $mid, int $right): array {
    $leftSize = $mid - $left + 1;
    $rightSize = $right - $mid;
    $leftArray = [];
    $rightArray = [];
    for ($i = 0; $i < $leftSize; $i++) {
        $leftArray[$i] = $arr[$left + $i];
    }
    for ($i = 0; $i < $rightSize; $i++) {
        $rightArray[$i] = $arr[$mid + 1 + $i];
    }
    $i = 0;
    $j = 0;
    $k = $left;
    while ($i < $leftSize && $j < $rightSize) {
        if ($leftArray[$i] <= $rightArray[$j]) {
            $arr[$k] = $leftArray[$i];
            $i++;
        } else {
            $arr[$k] = $rightArray[$j];
            $j++;
        }
        $k++;
    }
    while ($i < $leftSize) {
        $arr[$k] = $leftArray[$i];
        $i++;
        $k++;
    }
    while ($j < $rightSize) {
        $arr[$k] = $rightArray[$j];
        $j++;
        $k++;
    }
    return $arr;
}

Сортировка слиянием — это мощный алгоритм сортировки, временная сложность которого составляет O(n log n). В этой статье мы исследовали два разных метода реализации сортировки слиянием в PHP: рекурсивный подход и итеративный подход. Рекурсивный метод является наиболее распространенным и интуитивно понятным, а итерационный метод представляет собой альтернативу для тех, кто предпочитает итеративное решение. Поняв и реализовав сортировку слиянием, вы сможете эффективно сортировать большие массивы или списки в PHP.