Процесс слияния на месте:

Question

Процедура слияния в MergeSort не может выполняться на месте.Это мое объяснение:

Сложно ли это?

A = 5,1,9,2,10,0

”q”: указатель на серединумассив с индексом 2.

Мы объединяем элемент в точке q и элемент слева от элементов справа от q.

A = 1,5,10,0,2,12

Мы указываем на начало левой стороны с помощью «i», а справа - на «j».

Мы указываем на текущую позицию в массиве с помощью «k».

Алгоритм начинается с i = 0, j = 3, k = 0.

Если объединить на месте: для k = 0: i = 0, j = 3,0 <1-> A [k] = A [j] andj + +

результирующий массив: A = {0,5,10,0,2,12}

Как мы видим, мы уже потеряли значение 1.

Мы продолжим терять значения, например, на следующей итерации:

для k = 1: i =0, j = 4,0 <2 = ⇒A [k] = A [i] andi + + </p>

результирующий массив: A = {0,0,10,0,2,12}

Answer 1

Это можно сделать с помощью поворота подмассивов.Существуют сортировки слиянием со сложностью времени O (n log (n)), но они используют часть массива в качестве рабочего хранилища.Если требуется стабильность, то для предоставления пространства используется небольшое подмножество уникальных значений (например, 2 sqrt (n)), поскольку переупорядочение уникальных значений перед сортировкой не нарушит стабильность.Возвращаясь к простому алгоритму вращения:

 1  5 10  0  2 12
 0  1  5 10  2 12         0 <  1, rotate  0 into place, adjust working indexes
 0  1  5 10  2 12         1 <  2, continue
 0  1  2  5 10 12         2 <  5, rotate  2 into place, adjust working indexes
 0  1  2  5 10 12         5 < 12, continue
 0  1  2  5 10 12        10 < 12, continue, end of left run, done