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

😎 Решение:

using System;

class Program {
    static void MergeSort(int[] nums) {
        if (nums.Length > 1) {
            int mid = nums.Length / 2;
            int[] left_half = new int[mid];
            int[] right_half = new int[nums.Length - mid];

            Array.Copy(nums, 0, left_half, 0, mid);
            Array.Copy(nums, mid, right_half, 0, nums.Length - mid);

            MergeSort(left_half);
            MergeSort(right_half);

            int i = 0, j = 0, k = 0;
            while (i < left_half.Length && j < right_half.Length) {
                if (left_half[i] < right_half[j]) {
                    nums[k++] = left_half[i++];
                } else {
                    nums[k++] = right_half[j++];
                }
            }

            while (i < left_half.Length) {
                nums[k++] = left_half[i++];
            }

            while (j < right_half.Length) {
                nums[k++] = right_half[j++];
            }
        }
    }
}

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