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

😎 Решение:

def mergeSort(nums):
    if len(nums) > 1:
        mid = len(nums) // 2
        left_half = nums[:mid]
        right_half = nums[mid:]

        mergeSort(left_half)
        mergeSort(right_half)

        i = j = k = 0
        while i < len(left_half) and j < len(right_half):
            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 < len(left_half):
            nums[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            nums[k] = right_half[j]
            j += 1
            k += 1

    return nums

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