📚 آموزش الگوریتم مرتب‌سازی ادغامی (Merge Sort)

سلام دوستان! امروز قصد داریم یکی از الگوریتم‌های مهم و پرکاربرد در علوم کامپیوتر که در دانشگاه‌ها تدریس می‌شود را به شما آموزش دهیم. این الگوریتم به نام مرتب‌سازی ادغامی (Merge Sort) شناخته می‌شود. بیایید با هم یاد بگیریم چطور این الگوریتم کار می‌کند. 🧠✨

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

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

پیاده‌سازی الگوریتم
برای درک بهتر، به کد زیر توجه کنید که این الگوریتم را به زبان پایتون پیاده‌سازی کرده است:

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

    return arr

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

مزایا و معایب
✅ مزایا:
- پیچیدگی زمانی مناسب
- عملکرد قابل پیش‌بینی

❌ معایب:
- نیاز به حافظه اضافی برای لیست‌های نیمه

امیدوارم این آموزش برای شما مفید بوده باشد! تا آموزش بعدی، موفق و پیروز باشید! 🌟

#الگوریتم #مرتب_سازی #برنامه_نویسی #کامپیوتر #آموزش #MergeSort