Задача: 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⃣Слить две отсортированные половины.

😎 Решение:

func mergeSort(_ nums: inout [Int]) {
    if nums.count > 1 {
        let mid = nums.count / 2
        var left_half = Array(nums[0..<mid])
        var right_half = Array(nums[mid..<nums.count])

        mergeSort(&left_half)
        mergeSort(&right_half)

        var i = 0, j = 0, k = 0
        while i < left_half.count && j < right_half.count {
            if left_half[i] < right_half[j] {
                nums[k] = left_half[i]
                i += 1
            } else {
                nums[k] = right_half[j]
                j += 1
            }
            k += 1
        }

        while i < left_half.count {
            nums[k] = left_half[i]
            i += 1
            k += 1
        }

        while j < right_half.count {
            nums[k] = right_half[j]
            j += 1
            k += 1
        }
    }
}

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