مرتب سازی ادغامی

مرتب سازی ادغامی

ادغام، یک فرایند مرتبط به مرتب سازی است. ادغام دو طرفه به معنای ترکیب دو آرایه مرتب شده در یک آرایه مرتب است. با به کاری گیری مکرر روال ادغام، می توان آرایه ای را مرتب کرد. برای مثال جهت مرتب سازی آرایه ای از 16 عنصر می توان آن را به دو زیر آرایه تبدیل کرد که تعداد عناصر هر کدام، 8 است، سپس دو زیر آرایه را مرتب کرده آن ها را ادغام می کنیم تا یک آرایه مرتب شده ایجاد گردد. به همین شیوه می توان هر یک از زیر آرایه های 8 عنصری را به دو زیر آرایه 4 عنصر تقسیم کرد و آن ها را مرتب سازی و ادغام نمود. در نهایت همه زیر آرایه ها یک عنصری می شوند و آرایه  ای به اندازه 1 طبعا مرتب است. این روش را مرتب سازی ادغامی می گویند. برای آرایه n  عنصری ، مرتب سازی ادغامی شامل مراحل زیر می شود ( برای سهولت فرض می کنیم n  توانی از 2 باشد ) :
1.    تقسیم آرایه به دو زیر آرایه، هر یک با 2/ n عنصر.
2.    حل زیر آرایه با مرتب سازی آن. اگر زیر آرایه به قدر کافی کوچک نبود، برای حل آن را از بازگشتی استفاده می کنیم.
3.    ترکیب حل زیر آرایه ها از طریق ادغام آن ها در یک آرایه مرتب.