مرتب سازی ادغامی، حل مسئله را به چند قسمت تبدیل کرده و آن ها را جدا حل میکند. به همین سبب از چندین تابع برخوردار است و متوسط عملکرد آن از رابطه O(n log n) بدست می آید. سورس این الگوریتم در ادامه مطلب قرار داده شده است .
همانطور که در شکل فوق مشاهده می شود، الگوریتم merge sort از دو بخش Divide و Merge تشکیل می شود. زمانی که یک آرایه از اعداد جهت sort کردن به روش در اختیار ما قرار داده می شود، ابتدا آرایه را به دو آرایه با طول n/2 تقسیم می کنیم. دقت کنید که این عمل تقسیم سازی آرایه را در دو زیر آرایه حاصل و تمام زیر آرایه های دیگر حاصل از مراحل تقسیم سازی قبلی نیز اعمال می کینم تا جایکه زیر آرایه های حاصل تک عضوی گردند. سپس نوبت به انجام عملیات merge کردن می رسد. در این مرحله هر دو زیر آرایه تک عضوی را sort کرده و سپس merge می نماییم. نتیجه این عمل تشکیل یک زیر آرایه مرتب شده خواهد بود. عملیات merge کردن را تا جایی ادامه می دهیم تا آرایه اولیه «به صورت مرتب شده» حاصل شود.
«نکته» این الگوریتم مشابه الگوریتم مرتب سازی سریع یا quick sort، از روش تقسیم و حل یا divide-and-conquer strategy و با استفاده از تکنیک بازگشتی « Recursive » حل می گردد. البته این الگوریتم از طریق روش تکراری نیز قابل پیاده سازی می باشد.
بررسی پیچیدگی زمانی الگوریتم
همانگونه که مشاهده می شود، سرعت الگوریتم در بدترین حالت آن هم خوب است. ولی از لحاظ مصرف حافظه اشکال عمده آن این است که به یک بافر به اندازه آرایه اولیه نیاز دارد. این عیب یا نارسایی در مورد آرایه های بزرگ بویژه اگر عناصر آرایه از نوع Structure باشد، بسیار محسوس تر می شود.
فیلم آموزشی مرتبط – روی لینک زیر کلیک کنید
merc
نشانی ایمیل شما منتشر نخواهد شد. بخشهای موردنیاز علامتگذاری شدهاند *
Current ye@r *
Leave this field empty
Copyright © 2010 Dlbook Team