الگوریتم مرتب سازی ادغامی چیست؟ — تشریح + پیاده سازی

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

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

الگوریتم مرتب‌سازی ادغامی «Merge Sort» یک الگوریتم مرتب‌سازی مقایسه‌ای است که از روش تقسیم و حل «Divide and Conquer» برای مرتب‌سازی داده‌ها استفاده می‌کند. این الگوریتم ابتدا لیست داده‌ها را به صورت بازگشتی به زیرلیست‌های کوچکتر تقسیم می‌کند تا هر زیرلیست شامل یک عنصر شود. سپس، زیرلیست‌ها را به صورت مرتب شده با هم ادغام «Merge» می‌کند تا لیست مرتب شده نهایی به دست آید. مرتب‌سازی ادغامی به دلیل داشتن پیچیدگی زمانی O(n log n) در همه حالات «بهترین، متوسط و بدترین»، یک الگوریتم کارآمد برای مرتب‌سازی مجموعه‌های بزرگ داده است و پایداری آن (حفظ ترتیب عناصر هم‌ارزش» از دیگر مزایای آن محسوب می‌شود.

مرتب‌سازی ادغامی چگونه کار می‌کند؟

در این قسمت از مقاله الگوریتم مرتب سازی ادغامی گام به گام نحوه‌ی عملکرد مرتب‌سازی ادغامی می‌پردازیم:

• تقسیم: لیست یا آرایه را به صورت بازگشتی به دو نیمه تقسیم کنید تا جایی که دیگر نتوان آن را تقسیم کرد.
• غلبه: هر زیرآرایه به طور جداگانه با استفاده از الگوریتم مرتب‌سازی ادغامی مرتب می‌شود.
• ادغام: زیرآرایه‌های مرتب شده به ترتیب مرتب شده با هم ادغام می‌شوند. این فرآیند تا زمانی ادامه می‌یابد که تمام عناصر هر دو زیرآرایه ادغام شده باشند.

مثالی از روند پیاده سازی الگوریتم مرتب سازی ادغامی

بیایید آرایه یا لیست [۳۸, ۲۷, ۴۳, ۱۰] را با استفاده از مرتب‌سازی ادغامی مرتب کنیم.

تقسیم:

• [۳۸, ۲۷, ۴۳, ۱۰] به [۳۸, ۲۷] و [۴۳, ۱۰] تقسیم می‌شود.
• [۳۸, ۲۷] به [۳۸] و [۲۷] تقسیم می‌شود.
• [۴۳, ۱۰] به [۴۳] و [۱۰] تقسیم می‌شود.

غلبه:

• [۳۸] از قبل مرتب است.
• [۲۷] از قبل مرتب است.
• [۴۳] از قبل مرتب است.
• [۱۰] از قبل مرتب است.

ادغام:

• [۳۸] و [۲۷] را ادغام کنید تا [۲۷, ۳۸] به دست آید.
• [۴۳] و [۱۰] را ادغام کنید تا [۱۰, ۴۳] به دست آید.
• [۲۷, ۳۸] و [۱۰, ۴۳] را ادغام کنید تا لیست مرتب شده نهایی [۱۰, ۲۷, ۳۸, ۴۳] به دست آید.

بنابراین، لیست مرتب شده [۱۰, ۲۷, ۳۸, ۴۳] است.

رابطه بازگشتی مرتب‌سازی ادغامی

رابطه بازگشتی مرتب‌سازی ادغامی به صورت زیر است:

T(n) = { Θ(۱)  اگر n=1
        { 2T(n/2) + Θ(n) اگر n>1

در اینجا:

T(n) نشان‌دهنده مجموع زمانی است که الگوریتم برای مرتب‌سازی یک آرایه به اندازه n صرف می‌کند.
2T(n/2) نشان‌دهنده زمانی است که الگوریتم برای مرتب‌سازی بازگشتی دو نیمه آرایه صرف می‌کند. از آنجایی که هر نیمه n/2 عنصر دارد، دو فراخوانی بازگشتی با اندازه ورودی n/2 داریم.
Θ(n) نشان‌دهنده زمانی است که برای ادغام دو نیمه مرتب شده صرف می‌شود.

تحلیل پیچیدگی مرتب‌سازی ادغامی

پیچیدگی زمانی:

• بهترین حالت: O(n log n)، زمانی که آرایه از قبل مرتب یا تقریباً مرتب باشد.
• حالت متوسط: O(n log n)، زمانی که آرایه به صورت تصادفی مرتب شده باشد.
• بدترین حالت: O(n log n)، زمانی که آرایه به صورت معکوس مرتب شده باشد.
• فضای کمکی: O(n)، فضای اضافی برای آرایه موقت مورد استفاده در طول ادغام مورد نیاز است.

مزایا و معایب مرتب‌سازی ادغامی (Merge Sort)

مزایا:

• پایدار (Stability): مرتب‌سازی ادغامی یک الگوریتم مرتب‌سازی پایدار است. این یعنی ترتیب نسبی عناصر برابر در آرایه ورودی، حفظ می‌شود. به عبارت دیگر، اگر دو عنصر با مقدار یکسان داشته باشیم، ترتیب آن‌ها پس از مرتب‌سازی هم مانند قبل باقی می‌ماند.
• عملکرد تضمین‌شده در بدترین حالت: مرتب‌سازی ادغامی در بدترین حالت هم پیچیدگی زمانی O(N log N) دارد. این یعنی حتی برای مجموعه‌های داده بزرگ هم عملکرد خوبی دارد و زمان اجرای آن به طور قابل پیش‌بینی افزایش می‌یابد.
• پیاده‌سازی ساده: رویکرد تقسیم و حل (Divide and Conquer) این الگوریتم، پیاده‌سازی آن را نسبتاً آسان و سرراست می‌کند.
• طبیعتاً موازی‌پذیر (Naturally Parallel): از آنجایی که زیرآرایه‌ها به صورت مستقل ادغام می‌شوند، مرتب‌سازی ادغامی برای پردازش موازی بسیار مناسب است و می‌توان آن را به راحتی به صورت موازی اجرا کرد تا سرعت اجرای آن افزایش یابد.

معایب:

• پیچیدگی فضایی: مرتب‌سازی ادغامی برای ذخیره زیرآرایه‌های ادغام‌شده در طول فرایند مرتب‌سازی، به حافظه اضافی نیاز دارد.
• غیرمستقیم (Not in-place): مرتب‌سازی ادغامی یک الگوریتم مرتب‌سازی درجا (in-place) نیست. این یعنی برای ذخیره داده‌های مرتب‌شده به حافظه اضافی نیاز دارد. این می‌تواند در برنامه‌هایی که مصرف حافظه یک نگرانی مهم است، یک نقطه ضعف محسوب شود.
• کندتر از مرتب‌سازی سریع (QuickSort): به طور کلی، مرتب‌سازی ادغامی از مرتب‌سازی سریع کندتر است. دلیلش این است که مرتب‌سازی سریع به دلیل کار کردن درجا، با حافظه کش (Cache) بهتر کار می‌کند. (مرتب‌سازی سریع به طور موثرتری از حافظه کش استفاده می‌کند).

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

الگوریتم مرتب‌سازی ادغامی (Merge Sort) به دلیل ویژگی‌های خاص خود، کاربردهای متنوعی در زمینه‌های مختلف دارد. در اینجا به مهم‌ترین کاربردهای آن اشاره می‌کنم:

 مرتب‌سازی مجموعه‌ داده‌های بزرگ

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

 مرتب‌سازی خارجی (External Sorting)

هنگامی که حجم داده‌ها به قدری زیاد است که در حافظه اصلی (RAM) جا نمی‌شوند، از مرتب‌سازی خارجی استفاده می‌شود. مرتب‌سازی ادغامی به دلیل امکان پردازش داده‌ها به صورت ترتیبی (sequential)، برای این منظور بسیار مناسب است. داده‌ها به قطعات کوچک‌تر تقسیم شده، مرتب شده و سپس به صورت ترتیبی با هم ادغام می‌شوند.

مرتب‌سازی لیست‌های پیوندی (Linked Lists)

مرتب‌سازی ادغامی برای مرتب‌سازی لیست‌های پیوندی بسیار کارآمد است. در مقایسه با آرایه‌ها، دسترسی ترتیبی به عناصر لیست پیوندی، مرتب‌سازی ادغامی را به گزینه مناسب‌تری تبدیل می‌کند.

شمارش وارونگی‌ها (Counting Inversions)

الگوریتم مرتب‌سازی ادغامی را می‌توان برای شمارش تعداد وارونگی‌ها در یک آرایه استفاده کرد. یک وارونگی زمانی رخ می‌دهد که دو عنصر در آرایه در ترتیب اشتباه قرار داشته باشند (یعنی i < j اما A[i] > A[j]).

پایداری (Stability)

همانطور که قبلاً ذکر شد، مرتب‌سازی ادغامی یک الگوریتم پایدار است. این ویژگی در مواردی که حفظ ترتیب عناصر با مقادیر یکسان اهمیت دارد، بسیار ارزشمند است. به عنوان مثال، اگر لیستی از دانش‌آموزان را بر اساس نمره و سپس بر اساس نام مرتب کنیم، پایداری مرتب‌سازی ادغامی تضمین می‌کند که ترتیب دانش‌آموزان با نمره یکسان، بر اساس نام حفظ می‌شود.

مرتب‌سازی داده‌های در حال ورود

اگر داده‌ها به صورت پیوسته و با نرخ نسبتا پایینی وارد می‌شوند، مرتب‌سازی ادغامی می‌تواند به صورت آنلاین و بدون نیاز به ذخیره کل داده‌ها در حافظه، به‌طور مستمر آن‌ها را مرتب کند. این کاربرد در سیستم‌های پایگاه داده و پردازش داده‌های زنده بسیار مفید است.

پردازش و تحلیل داده‌های توزیع شده

در محیط‌های محاسباتی توزیع شده، که داده‌ها بر روی چندین کامپیوتر پخش شده‌اند، مرتب‌سازی ادغامی به راحتی قابل تطبیق و پیاده‌سازی برای ادغام نتایج مرتب‌سازی از روی ماشین‌های مختلف است. این باعث می‌شود در پردازش حجم بسیار زیاد داده‌ها کارآمد باشد.

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

در فرآیندهای ادغام داده‌ها یا هم‌زمان‌سازی پایگاه‌های داده، نیاز به ادغام و مرتب‌سازی داده‌های مختلف از چندین منبع وجود دارد. مرتب‌سازی ادغامی، روش خوبی برای ادغام این داده‌ها و دستیابی به نظم مطلوب است.

طراحی الگوریتم‌های جستجو

مرتب‌سازی ادغامی، گاهی پیش‌نیاز برای الگوریتم‌های جستجوی پیشرفته است. به عنوان مثال، جستجوی دودویی برای یافتن عنصری در یک آرایه مرتب شده، وابسته به پیش‌نیاز مرتب‌سازی داده‌ها است و مرتب‌سازی ادغامی، یکی از روش‌های مناسب برای این هدف است.

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

کد زیر دو زیرآرایه با مرزهای «left ، mid و right» را به عنوان ورودی می‌پذیرد. سپس، دو آرایه موقت «L و R» ایجاد می‌کند و داده‌های زیرآرایه‌ها را در آنها کپی می‌کند. در ادامه، دو نشانگر «i و j» برای پیمایش «L و R» و نشانگر «k» برای قرار دادن عناصر در آرایه اصلی استفاده می‌شوند. در حلقه while، عناصر «L و R» مقایسه می‌شوند و کوچک‌تر آنها به آرایه اصلی در مکان «k» قرار داده می‌شود. این عمل تا زمانی ادامه می‌یابد که یکی از زیرآرایه‌ها خالی شود. در نهایت، عناصر باقی‌مانده در زیرآرایه‌های دیگر به آرایه اصلی اضافه می‌شوند.

#include <bits/stdc++.h>
using namespace std;

// Merges two subarrays of arr[].
// First subarray is arr[left..mid]
// Second subarray is arr[mid+1..right]
void merge(vector<int>& arr, int left, 
                     int mid, int right)
{
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Create temp vectors
    vector<int> L(n1), R(n2);

    // Copy data to temp vectors L[] and R[]
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0;
    int k = left;

    // Merge the temp vectors back 
    // into arr[left..right]
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy the remaining elements of L[], 
    // if there are any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy the remaining elements of R[], 
    // if there are any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// begin is for left index and end is right index
// of the sub-array of arr to be sorted
void mergeSort(vector<int>& arr, int left, int right)
{
    if (left >= right)
        return;

    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

// Function to print a vector
void printVector(vector<int>& arr)
{
    for (int i = 0; i < arr.size(); i++)
        cout << arr[i] << " ";
    cout << endl;
}

// Driver code
int main()
{
    vector<int> arr = { 12, 11, 13, 5, 6, 7 };
    int n = arr.size();

    cout << "Given vector is \n";
    printVector(arr);

    mergeSort(arr, 0, n - 1);

    cout << "\nSorted vector is \n";
    printVector(arr);
    return 0;
}

خروجی

Given array is 
۱۲ ۱۱ ۱۳ ۵ ۶ ۷ 

Sorted array is 
۵ ۶ ۷ ۱۱ ۱۲ ۱۳

 پیاده سازی الگوریتم مرتب سازی ادغامی (Merge Sort) به زبان پایتون

کد زیر، آرایه‌ای را که در بازه [left, right] قرار دارد، به دو زیرآرایه چپ (L) و راست (R) تقسیم می‌کند. سپس، هر دو زیرآرایه را مرتب می‌کند و در نهایت، آن‌ها را به صورت مرتب شده در آرایه اصلی ادغام می‌کند. در واقع، این تابع قسمت ادغام را در الگوریتم Merge Sort انجام می‌دهد و دو زیرآرایه مرتب شده را به یک آرایه مرتب بزرگ‌تر ادغام می‌کند.

def merge(arr, left, mid, right):
    n1 = mid - left + 1
    n2 = right - mid

    # Create temp arrays
    L = [0] * n1
    R = [0] * n2

    # Copy data to temp arrays L[] and R[]
    for i in range(n1):
        L[i] = arr[left + i]
    for j in range(n2):
        R[j] = arr[mid + 1 + j]

    i = 0  # Initial index of first subarray
    j = 0  # Initial index of second subarray
    k = left  # Initial index of merged subarray

    # Merge the temp arrays back
    # into arr[left..right]
    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    # Copy the remaining elements of L[],
    # if there are any
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    # Copy the remaining elements of R[], 
    # if there are any
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1

def merge_sort(arr, left, right):
    if left < right:
        mid = (left + right) // 2

        merge_sort(arr, left, mid)
        merge_sort(arr, mid + 1, right)
        merge(arr, left, mid, right)

def print_list(arr):
    for i in arr:
        print(i, end=" ")
    print()

# Driver code
if __name__ == "__main__":
    arr = [12, 11, 13, 5, 6, 7]
    print("Given array is")
    print_list(arr)

    merge_sort(arr, 0, len(arr) - 1)

    print("\nSorted array is")
    print_list(arr)

خروجی

Given array is 
۱۲ ۱۱ ۱۳ ۵ ۶ ۷ 

Sorted array is 
۵ ۶ ۷ ۱۱ ۱۲ ۱۳

 پیاده سازی الگوریتم مرتب سازی ادغامی (Merge Sort) به زبان جاوا

در کد زیر، تابع «merge» دو زیر آرایه از آرایه «arr» را ادغام می‌کند. ابتدا اندازه دو زیر آرایه با محاسبه «n1 و n2» مشخص می‌شود. سپس، دو آرایه موقت «L و R» با اندازه‌های «n1 و n2» برای ذخیره زیر آرایه‌ها ایجاد می‌شوند. داده‌های زیر آرایه‌ها در آرایه‌های موقت کپی می‌شوند. در ادامه (قسمتی که در کد داده نشده است) دو آرایه موقت ادغام می‌شوند و به ترتیب صعودی در آرایه اصلی قرار می‌گیرند. این تابع، نقش کلیدی در مرتب‌سازی ادغامی را ایفا می‌کند، زیرا دو زیر آرایه مرتب شده را به یک آرایه مرتب شده بزرگتر ادغام می‌کند.

// Java program for Merge Sort
import java.io.*;

class GfG {

    // Merges two subarrays of arr[].
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    static void merge(int arr[], int l, int m, int r)
    {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;

        // Create temp arrays
        int L[] = new int[n1];
        int R[] = new int[n2];

        // Copy data to temp arrays
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];

        // Merge the temp arrays

        // Initial indices of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged subarray array
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            }
            else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // Copy remaining elements of L[] if any
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        // Copy remaining elements of R[] if any
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // Main function that sorts arr[l..r] using
    // merge()
    static void sort(int arr[], int l, int r)
    {
        if (l < r) {

            // Find the middle point
            int m = l + (r - l) / 2;

            // Sort first and second halves
            sort(arr, l, m);
            sort(arr, m + 1, r);

            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }

    // A utility function to print array of size n
    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    // Driver code
    public static void main(String args[])
    {
        int arr[] = { 12, 11, 13, 5, 6, 7 };

        System.out.println("Given array is");
        printArray(arr);

        sort(arr, 0, arr.length - 1);

        System.out.println("\nSorted array is");
        printArray(arr);
    }
}

خروجی

Given array is
۱۲ ۱۱ ۱۳ ۵ ۶ ۷ 

Sorted array is
۵ ۶ ۷ ۱۱ ۱۲ ۱۳

سخن آخر

الگوریتم مرتب‌سازی ادغامی (Merge Sort) یک الگوریتم مرتب‌سازی مبتنی بر تقسیم و غلبه است که با پیچیدگی زمانی O(n log n) کار می‌کند. این پیچیدگی زمانی در مقایسه با الگوریتم‌های مرتب‌سازی مبتنی بر مقایسه دیگر مانند مرتب‌سازی حبابی یا مرتب‌سازی انتخابی که پیچیدگی زمانی O(n^2) دارند، بسیار بهتر است. مرتب‌سازی ادغامی پایدار است و برای مرتب‌سازی داده‌های بزرگ، به خصوص در حافظه خارجی، مناسب است. از طرفی، استفاده از حافظه اضافی برای ایجاد آرایه‌های موقت، از معایب این روش است. در کل، مرتب‌سازی ادغامی به دلیل کارایی و ثباتش، یک الگوریتم مرتب‌سازی موثر و کاربردی در بسیاری از برنامه‌ها محسوب می‌شود.