***3
l Merge Sort:
lSort یکی از روش های مرتب سازی داخلی است.
lدر مرتب سازی به روش ادغام آرایه یا لیست مورد نظر طی چند مرحله به تعدادی آرایه یا لیست تک عضوی شکسته می شود.
نکات:تعداد آرایه ها یا لیست های تک عضوی همان تعداد اولیه ی نودها یا اعضای آرایه هستند .
طول لیست یا آرایه ی اولیه را Nدر نظر بگیرید.
به جای آرایه لیست به کار می بریم
***4
lMerge Sort:
lبعد از شکستن لیست،زیرلیست ها را با هم ادغام می کنیم و
زیرلیست های مرتب دیگری بدست می آوریم .
lزیر لیست های مرتب را طی چند مرحله با هم ادغام می کنیم تا به یک لیست مرتب با N عضو برسیم.
***6
lادغام دو لیست مرتب:
Initlist[l],…,initlist[m] initlist[m+1],…,initlist[n]
دو لیست مرتب شده از نوع Elementهستند، به طوری که:
Initlist [l].key≤…≤ initlist [m].key
Initlist[m+1].key ≤…≤ initlist [n].key
در تابع Mergeاین دو لیست مرتب با یکدیگر ادغام می شوندو
تابع مرتب شده ی جدیدی به نام MergedList ایجاد می شود.
***19
مرتب سازی ادغام به صورت تکرار (غیر بازگشتی )
دراین نسخه ورودی n لیست به طول 1است.این لیست ها دوبه دوبا هم ادغام می شوند تا n/2 لیست که طول هر یک از آن ها 1 است به دست آید (اگر n فرد باشد آنگاه یک لیست به طول 1 داریم). این n/2 لیست دوبه دو با هم ادغام می شوند و این فرایند تا آنجا ادامه می یابد که در انتها به یک لیست برسیم.
در اسلاید بعدی این فرایند نشان داده شده است.
***21
lآنجا که مرتب سازی ادغام شامل چند مرحله است از این رو بهتر است ابتدا تابعی برای این منظور معرفی کنیم:
MergePass Function
lپس از آن به معرفی MergeSort Algorithm می پردازیم که مرتب سازی را با احضار مکررتابع Merge Pass انجام می دهد.