Задание: Реализовать сортировку слиянием для работы с большими массивами данных. Продемонстрировать рекурсивное разделение массива и последующее слияние отсортированных подмассивов. Оценить использование дополнительной памяти.

Пример входных данных:

Массив: [38, 27, 43, 3, 9, 82, 10]
Порог переключения на сортировку вставками: 3 (для оптимизации)

Пример выходных данных:

Исходный массив: [38, 27, 43, 3, 9, 82, 10]

Процесс разделения:
  Делим [38, 27, 43, 3, 9, 82, 10]
    Левая часть: [38, 27, 43, 3]
      Делим [38, 27, 43, 3]
        Левая часть: [38, 27]
          Делим [38, 27]
            Левая часть: [38] (базовый случай)
            Правая часть: [27] (базовый случай)
          Сливаем [38] и [27] → [27, 38]
        Правая часть: [43, 3]
          Делим [43, 3]
            Левая часть: [43] (базовый случай)
            Правая часть: [3] (базовый случай)
          Сливаем [43] и [3] → [3, 43]
      Сливаем [27, 38] и [3, 43] → [3, 27, 38, 43]
    Правая часть: [9, 82, 10]
      Делим [9, 82, 10] (размер 3 ≤ порога, используем сортировку вставками)
      Сортировка вставками: [9, 82, 10] → [9, 10, 82]
  Сливаем [3, 27, 38, 43] и [9, 10, 82]

Процесс слияния (финальный шаг):
  Сравниваем 3 и 9 → берем 3
  Сравниваем 27 и 9 → берем 9
  Сравниваем 27 и 10 → берем 10
  Сравниваем 27 и 82 → берем 27
  Сравниваем 38 и 82 → берем 38
  Сравниваем 43 и 82 → берем 43
  Остаток правой части: [82]
  Результат: [3, 9, 10, 27, 38, 43, 82]

Отсортированный массив: [3, 9, 10, 27, 38, 43, 82]
Количество уровней рекурсии: 3
Использовано дополнительной памяти: 7 элементов (временный массив)

Вариант 1: Массив: [38, 27, 43, 3, 9, 82, 10]

Вариант 2: Массив: [64, 34, 25, 12, 22, 11, 90]

Вариант 3: Массив: [5, 1, 4, 2, 8]

Вариант 4: Массив: [100, 90, 80, 70, 60, 50, 40, 30, 20, 10]

Вариант 5: Массив: [3, 6, 1, 8, 4, 9, 2, 7, 5]

Вариант 6: Массив: [45, 23, 67, 12, 89, 34, 56, 78]

Вариант 7: Массив: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Вариант 8: Массив: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

Вариант 9: Массив: [29, 10, 14, 37, 13, 25, 48, 7]

Вариант 10: Массив: [55, 33, 77, 11, 99, 44, 66, 22, 88]

Вариант 11: Массив: [15, 25, 35, 45, 55, 65, 75, 85, 95]

Вариант 12: Массив: [95, 85, 75, 65, 55, 45, 35, 25, 15]

Вариант 13: Массив: [42, 17, 89, 63, 31, 76, 24, 58]

Вариант 14: Массив: [8, 3, 1, 6, 9, 2, 7, 4, 5]

Вариант 15: Массив: [100, 50, 25, 75, 12, 37, 62, 87]

Вариант 16: Массив: [19, 28, 37, 46, 55, 64, 73, 82, 91]

Вариант 17: Массив: [91, 82, 73, 64, 55, 46, 37, 28, 19]

Вариант 18: Массив: [6, 2, 9, 4, 7, 1, 8, 3, 5]

Вариант 19: Массив: [33, 66, 99, 11, 44, 77, 22, 55, 88]

Вариант 20: Массив: [14, 27, 39, 52, 65, 78, 81, 93]

Дополнительные параметры (выбрать в соответствии с вариантом):

• Варианты 1-4: Без оптимизации (чистое рекурсивное слияние)
• Варианты 5-8: С оптимизацией (использовать сортировку вставками для подмассивов размером ≤ 4)
• Варианты 9-12: С визуализацией использования памяти (показывать выделение временных массивов)
• Варианты 13-16: Итеративная реализация (снизу-вверх) без рекурсии
• Варианты 17-20: Внешняя сортировка (работа с файлами, имитация больших данных)

Примечание: Для вариантов 17-20 считать, что массив не помещается в оперативную память, и реализовать слияние временных файлов на диске.