Сортировка естественным слиянием. Идея сортировки состоит в следующем

Begin

A[i]:=A[i+nCurr];

// nMove:=nMove+2;

end;

end;

Идея сортировки состоит в следующем.

Сортируемый массив из элементов разбивается на подмассивы, каждый из которых «случайно» оказался отсортированным. Пусть имеется в виду сортировка по возрастанию Тогда правая граница подмассива – это индекс элемента массива, который является последним или после которого возрастание «вдруг» сменяется убыванием.

Такой частично упорядоченный массив получается простым соединением в одну длинную цепь таких наборов элементов, где каждый набор уже был сознательно отсортирован.

Даже если массив не упорядочивался частично, вероятность, что все отсортированные подмассивы состоят из одного элемента, достаточно мала.

Слушателям предлагается самостоятельно оценить, чему именно равна такая вероятность.

Дата добавления: 2014-01-04