وبلاگ رسمی مهدی غلامی میاندهی

الگوریتم مرتب سازی ادغامی (Merge Sort) در ++C

مرتب سازی ادغامی، حل مسئله را به چند قسمت تبدیل کرده و آن ها را جدا حل میکند. به همین سبب از چندین تابع برخوردار است و متوسط عملکرد آن از رابطه (O(n log n بدست می آید. سورس این الگوریتم در ادامه مطلب قرار داده شده است .

ویژگی‌های مرتب‌سازی ادغامی

1- پیچیدگی زمانی اجرای الگوریتم در تمامی حالات ( Ө( n log n است. چرا که این الگوریتم تحت هر شرایطی آرایه را به دو قسمت کرده و مرتب‌سازی را انجام می‌دهد.

2- پیچیدگی حافظه مصرفی بستگی به روش پیاده‌سازی مرحله ادغام دارد، که تا ( O( n افزایش می‌یابد. پیاده‌سازی درجای این الگوریتم حافظه مصرفی مرتبه ( Ө( 1 دارد. اما اجرای آن در بدترین حالت زمانبر است.

3- الگوربتم مرتب‌سازی ادغامی با پیاده‌سازی فوق یک روش پایدار است. چنین الگوریتمی ترتیب عناصر با مقدار یکسان را پس از مرتب‌سازی حفظ می‌کند.