Я изучал алгоритм сортировки слиянием, и я не могу заключить, сколько массивов действительно создано как часть алгоритма. В некоторых литературе говорится, что весь исходный массив копируется в новый массив, который отсортирован. Но это означает, что было создано только 2 массива.Проблемы с пониманием того, сколько массивов действительно создано в алгоритме сортировки слиянием.
Насколько я понимаю, алгоритм сортировки слияния имеет 2 основных шага. Разделение и слияние. Я думал, что если вы дадите слияние сортировать массив из 100 слотов, он фактически создает новые массивы, поскольку он разбивается по середине от 100> 50/50> 25/25> 12/13> 6/5> 3/3> 1/1 , После всех этих расщеплений в этой точке у него есть 12 или 13 массивов в памяти. И затем, когда он, наконец, копирует их все в новые массивы из 1> 2> 3 или 4> 6> 12> 25> 50> 100.
Это еще 8 массивов (грубо говоря).
Но в учебниках я читаю такие вещи, как это:
Вы можете задаться вопросом, где все эти Подмассивы расположены в памяти. В алгоритме массив рабочих пространств того же размера, что и исходный массив, создан . Subarrays хранятся в разделах массива рабочей области. Это означает, что подмассивы в исходном массиве копируются в соответствующие места в массиве рабочей области. После каждого слияния массив рабочих пространств копируется обратно в исходный массив.
- Структуры и алгоритмы в Java Data Роберт Лафоре
Вы можете реализовать сортировку слияния на месте: http://stackoverflow.com/q/2571049/ 3788176. Или нет. Таким образом, количество создаваемых массивов зависит от реализации. –
Эти комментарии не дают достаточно подробностей. Конечно, это зависит от реализации. Но предположим, что это не сортировка слияния (Rocket Science). Это основная сортировка слияния в CS101, затем сколько массивов создается? – Doublespeed