Образовательный ресурс edu.irnok.net

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Сортировка слиянием для больших массивов ======

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

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

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

</code>

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

<code>
Исходный массив: [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 элементов (временный массив)

</code>


**Вариант 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 считать, что массив не помещается в оперативную память, и реализовать слияние временных файлов на диске.