Задача: 912. Sort an Array
Сложность: medium

Задав массив целых чисел nums, отсортируйте массив по возрастанию и верните его. Вы должны решить задачу без использования встроенных функций за время O(nlog(n)) и с минимально возможной пространственной сложностью.

Пример:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]

👨‍💻 Алгоритм:

1⃣Используем алгоритм "Сортировка слиянием" (Merge Sort), который обеспечивает время выполнения O(n log n) и минимально возможную пространственную сложность для стабильного сортировочного алгоритма.

2⃣Разделить массив на две половины.
Рекурсивно отсортировать каждую половину.

3⃣Слить две отсортированные половины.

😎 Решение:

function mergeSort(&$nums) {
    if (count($nums) > 1) {
        $mid = count($nums) / 2;
        $left_half = array_slice($nums, 0, $mid);
        $right_half = array_slice($nums, $mid);

        mergeSort($left_half);
        mergeSort($right_half);

        $i = $j = $k = 0;
        while ($i < count($left_half) && $j < count($right_half)) {
            if ($left_half[$i] < $right_half[$j]) {
                $nums[$k++] = $left_half[$i++];
            } else {
                $nums[$k++] = $right_half[$j++];
            }
        }

        while ($i < count($left_half)) {
            $nums[$k++] = $left_half[$i++];
        }

        while ($j < count($right_half)) {
            $nums[$k++] = $right_half[$j++];
        }
    }
}

Ставь 👍 и забирай 📚 Базу знаний