بررسي الگوريتم مرتب‌سازي ادغامي

ابتدا فهرستي از داده‌ها که قرار است مرتب شوند به 2 فهرست به طول مساوي تقسيم مي‌شوند و سپس فهرست‌هاي توليد شده به روش بازگشتي با صدا زدن تابع MergSort هر کدام به دو زيرفهرست تقسيم مي‌شوند. اين عمل آنقدر ادامه پيدا مي‌کند تا به فهرست‌هايي برسيم که طول هر کدام ? باشد.

تمام زيرفهرست‌هاي توليدشده مرتب مي‌شوند و سپس از پايين به بالا با فهرست‌هاي مجاور خود ادغام شده و فهرست جديدي توليد مي‌شود. اين فهرست‌ها نيز با فهرست‌هاي مجاور خود ادغام مي‌شوند. آن قدر اين فهرست‌ها با هم ترکيب مي‌شوند تا به فهرست نهايي برسيم. در هر ادغام مرتب بودن داده‌ها حفظ مي‌شود. حال اين روش را با يک مثال توضيح مي‌دهيم.

فرض کنيد داده‌هاي ما مجموعه‌اي به نام A‌ است که به‌صورت زير تعريف شده است:

A = { 5,2,4,7,1,3,2,6}

ابتدا مجموعه A را به 2 زيرمجموعه با طول يکسان به نام‌هاي A1و A2 تقسيم مي‌کنيم:

A1={5,2,4,7}, A2={ 1,3,2,6}

سپس هر کدام از اين مجموعه‌ها را به 2 مجموعه با طول مساوي تقسيم كرده و در نهايت به ? مجموعه به‌صورت زير مي‌رسيم:

B={5,2}, C={4,7}, D={1,3}, E={2,6}

از مجموعه‌هاي بالا فقط مجموعه B نياز به مرتب‌سازي دارد. پس از مرتب کردن جدول B بايد مجموعه‌ها را با هم ادغام کنيم.

عمل ادغام به اين صورت است که ابتدا اولين عنصر از هر دو مجموعه‌ را با هم مقايسه كرده و عنصر کوچک‌تر را در مجموعه سومي قرار مي‌دهيم که همان خروجي اين مرحله است. سپس عنصر بعدي را از همان مجموعه‌اي انتخاب مي‌کنيم که عنصر اول که در مجموعه سوم قرار گرفته است. سپس اين عمل را آنقدر ادامه مي‌دهيم که تمامي عناصر يکي از 2 مجموعه در مجموعه سومي که نتيجه حاصل از ادغام دو مجموعه در آن ذخيره شده ‌است، قرار بگيرد. سپس باقي عناصر مجموعه دوم به ترتيب به مجموعه سوم منتقل مي‌شود.

شبه‌کد اين الگوريتم به‌صورت زير است:

function merge_sort(m) {

var list left, right, result

if length(m) «= 1

return m

var middle = length(m) / 2

for each x in m up to middle

add x to left

for each x in m after middle

add x to right

left = merge_sort(left)

right = merge_sort(right)

result = merge(left, right)

return result

}

function merge(left, right) {

var list result

while length(left) » 0 and length(right) » 0

if first(left)«=first(right)

append first(left) to result

left = rest(left)

else

append first(right) to result

right = rest(right)

end while

while length(left) » 0

append left to result

while length(right) » 0

append right to result

return result}

T(N) = 2T(N/2) + N

در اين الگوريتم در هر مرحله آرايه به 2 آرايه شکسته مي‌شود و در هر مرحله از ادغام نيز بايد N مقايسه صورت بگيرد.