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

روش مرتب سازی ادغامی از الگوریتم تقسیم و حل (divide-and-conquer) و همچنین ادغام برای مرتب کردن داده‌ها استفاده می‌کند. در این الگوریتم مساله به چند جزء کوچک‌تر تقسیم می‌شود. هر کدوم از این قسمت‌ها رو به طور مجزا حل کرده، و با ترکیب اونها به مساله اصلی می‌رسیم. و اما طرح کلی مرتب سازی ادغام:

در این روش داده‌ها به دو قسمت مساوی تقسیم می‌شوند. و هر کدوم از این قسمت‌ها - به صورت بازگشتی - مرتب، و با ادغام آنها دادها بصورت کامل مرتب می‌شوند.اما توجه به این نکته ضروری است که اگر پس از یک بار تقسیم باز هم لیستهای ایجاد شده بزرگ باشند ، می توانیم برای هر زیر لیست مراحل بالا را دوباره انجام دهیم تا به زیر لیستهایی با تنها 1 عضو برسیم و واضح است که لیست تک عنصری خود مرتب است.

مرتب سازی سریع (Quick Sort) از جمله روشهای محبوب و با سرعت بالا برای مرتب کردن داده‌ها محسوب می‌شه. این روش هم مثل روش ادغام از تقسیم و حل (Divide and Conqure) برای مرتب کردن داده‌ها استفاده می‌کنه. به این ترتیب که داده‌ها رو به دو قسمت مجزا تقسیم، و با مرتب کردن اونها کل داده‌ها رو مرتب می‌کنه. برای اینکار یکی از داده‌ها (مثلاً داده اول) به عنوان محور انتخاب می‌شه. داده‌ها بر اساس محور طوری چینش می‌شن که همه داده‌های کوچک‌تر از محور سمت چپ و داده‌های بزرگ‌تر یا مساوی اون سمت راستش قرار می‌گیرن. با مرتب کردن دو قسمت به دست اومده کل داده‌ها مرتب می‌شن. در این حالت مثل روش ادغام نیازی به ادغام کردن داده‌ها نیست. چرا که قسمت سمت راست همگی از قسمت سمت چپ کوچک‌تر هستن و بالعکس.