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

الگوریتم مرتب‌سازی ادغامی یکی از الگوریتم‌های معروف مرتب‌سازی است که برای مرتب‌سازی داده‌ها از آن استفاده می‌شود. این الگوریتم بر مبنای تقسیم و حکم فراتر رفته (Divide and Conquer) عمل می‌کند و داده‌ها را به دو قسمت تقسیم می‌کند، هر دو را به طور مستقل مرتب می‌سازد و سپس نتایج را ترکیب می‌کند. این الگوریتم به خصوص در مواقعی کارآمد است که لیست‌ها بزرگ و نیاز به مرتب‌سازی پایدار دارند.

فرض کنید که می‌خواهیم یک لیست از اعداد را به صورت نزولی مرتب کنیم. مراحل اجرای الگوریتم مرتب‌سازی ادغامی به صورت زیر است:

1. تقسیم: لیست را به دو نیمه تقسیم می‌کنیم.
2. حکم: هر یک از دو نیمه را به صورت مستقل مرتب می‌کنیم. این مرتب‌سازی را با فراخوانی بازگشتی به‌کار می‌بریم.
3. ترکیب: دو نیمه مرتب‌شده را با یکدیگر ترکیب می‌کنیم تا لیست نهایی مرتب شود.

بیایید یک مثال ساده را مشاهده کنیم:

لیست ورودی: [38, 27, 43, 3, 9, 82, 10]

1. مرحله تقسیم:
   • نیمه اول: [38, 27, 43]
   • نیمه دوم: [3, 9, 82, 10]
2. مرحله حکم:
   • نیمه اول:
     • تقسیم: [38], [27, 43]
     • حکم: [27, 43] به صورت [27, 43] مرتب می‌شود.
     • ترکیب: [27, 43, 38] (لیست اصلی نیز مرتب شده است)
   • نیمه دوم:
     • تقسیم: [3, 9], [82, 10]
     • حکم: [3, 9] به صورت [3, 9] مرتب می‌شود.
     • حکم: [10, 82] به صورت [10, 82] مرتب می‌شود.
     • ترکیب: [3, 9, 10, 82] (لیست اصلی نیز مرتب شده است)
3. مرحله ترکیب:
   • لیست‌های مرتب‌شده [27, 38, 43] و [3, 9, 10, 82] را با یکدیگر ترکیب می‌کنیم.
   • نهایتاً لیست مرتب‌شده [3, 9, 10, 27, 38, 43, 82] حاصل می‌شود.
     کد Python برای اجرای الگوریتم مرتب‌سازی ادغامی در مثال بالا:

def merge_sort(arr):
    if len(arr) > 1:
        # مرحله تقسیم: تقسیم لیست به دو نیمه
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        # مرتب‌سازی دو نیمه به صورت مستقل (حکم)
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        # مرحله ترکیب: ترکیب دو نیمه مرتب‌شده
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

# مثال استفاده:
arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort(arr)
print("لیست مرتب‌شده:", arr)

این کد Python از تقسیم و حکم استفاده می‌کند تا لیست اعداد را مرتب کند. سپس مراحل تقسیم و حکم را به صورت بازگشتی انجام می‌دهد و در نهایت لیست مرتب‌شده را چاپ می‌کند.
الگوریتم مرتب‌سازی ادغامی به عنوان یکی از الگوریتم‌های مرتب‌سازی مقایسه‌ای به شمار می‌آید و در بدترین حالت نیز با پیچیدگی زمانی O(n log n) عمل می‌کند. این الگوریتم به خوبی برای مرتب‌سازی لیست‌های بزرگ و همچنین برای مرتب‌سازی پایدار مناسب است.