Сортировка слиянием

Сортировка слиянием

Сортировка слиянием - первая из встречающихся нам рекурсивных сортировок. В ее основе лежит замечание, согласно которому слияние двух отсортированных списков выполняется быстро. Список из одного элемента уже отсортирован, поэтому сортировка слиянием разбивает список на одноэлементные куски, а затем постепенно сливает их. Поэтому вся деятельность заключается в слиянии двух списков.
Сортировку слиянием можно записать в виде рекурсивного алгоритма, выполняющего работу, двигаясь вверх по рекурсии. При взгляде на нижеследующий алгоритм Вы увидите, что он разбивает список пополам до тех пор, пока номер первого элемента куска меньше номера последнего элемента в нем. Если же в очередном куске это условие не выполняется, это означает, что мы добрались до списка из одного элемента, который тем самым уже отсортирован. После возврата из двух вызовов процедуры MergeSort со списками длиной один вызывается процедура MergeLists, которая сливает эти два списка, в результате чего получается отсортированный список длины два. При возврате на следующий уровень два списка длины два сливаются в один отсортированный список длины 4. Этот процесс продолжается, пока мы не доберемся до исходного вызова, при котором две отсортированные половины списка сливаются в общий отсортированный список. Ясно, что процедура MergeSort разбивает список пополам при движении по рекурсии вниз, а затем на обратном пути сливает отсортированные половинки списка. Вот этот алгоритм:

MergeSort(list, first, last)
list				сортируемый список элементов
first				номер первого элемента в сортируемой части списка
last				номер последнего элемента в сортируемой части списка

if first < last then
	middle = (first + last) / 2
	MergeSort(list, first, middle)
	MergeSort(list, middle + 1, last)
	MergeLists(list, first, middle, middle + 1, last)
end if

Ясно, что всю работу проделывает функция MergeLists. Теперь займемся ею.
Пусть A и B - два списка, отсортированных в порядке возрастания. Такое упорядочивание означает, что первым элементом в каждом списке является наименьший элемент в нем, а последним - наибольший. Мы знаем, что при слиянии двух списков в один наименьший элемент в объединенном списке должен быть первым либо в части A, либо в части B, а наибольший элемент в объединенном списке должен быть последним либо в части A, либо в части B. Построение нового списка C, объединяющего списки A и B, мы начнем с того, что перенесем меньший из двух элементов A[1] и B[1] в C[1]. Но что должно попасть в C[2]? Если элемент A[1] оказался меньше, чем B[1], то мы перенесли его в C[1], и следующим по величине элементом может оказаться B[1] или A[2]. И тот, и другой вариант возможны, поскольку мы знаем только, что A[2] больше, чем A[1] и меньше, чем A[3], однако нам неизвестно отношение между величинами списка A и списка B. Похоже, что проще всего осуществить слияние, если завести два указателя, по одному на A и B, и увеличивать указатель того списка, очередной элемент в котором оказался меньше. Общая процедура продолжает сравнивать наименьшие элементы еще не просмотренных частей списков A и B и перемещать меньший из них в список C. В какой-то момент, однако, элементы в одном из списков A или B закончатся. В другом списке при этом останутся элементы, большие последнего элемента в первом списке. Нам необходимо переместить оставшиеся элементы в конец общего списка. В совокупности эти рассуждения приводят к следующему алгоритму:

MergeLists(list, start1, end1, start2, end2)
list				упорядочиваемый список элементов
start1				начало "списка" A
end1				конец "списка" A
start2				начало "списка" B
end2				конец "списка" B

// предполагается, что элементы списков A и B
// следуют в списке list друг за другом
finalStart = start1
finalEnd = end2
indexC = 1
while (start1 <= end1) and (start2 <= end2) do
	if list[start1] < list[start2] then
		result[indexC] = list[start1]
		start1 = start1 + 1
	else
		result[indexC] = list[start2]
		start2 = start2 + 1
	end if
	indexC = indexC + 1
end while

// перенос оставшейся части списка
if (start1 <= end1) then
	for i = start1 to end1 do
		result[indexC] = list[i]
		indexC = indexC + 1
	end for
else
	for i = start2 to end2 do
		result[indexC]	 = list[i]
		indexC = indexC + 1
	end for
end if

// возвращение результата в список
indexC = 1
for i = finalStart1 to finalEnd do
	list[i] = result[indexC]
	indexC = indexC + 1
end for

Сайт управляется системой uCoz