الگوریتم ادغام

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

def merge(a,b):
    c = []
    i = j = 0
    while i <len(a) and j <len(b):
        if a[i] <b[j]:
            c.append(a[i])
            i += 1
        else:
            c.append(b[j])
            j += 1
    while i <len(a):
        c.append(a[i])
        i += 1
    while j <len(b):
        c.append(b[j])
        j += 1
    return c

می‌خواهیم الگوریتمی ارائه دهیم که به عنوان ورودی ${\displaystyle k}$

برای ادغام ${\displaystyle k}$

الگوریتم اول

یک الگوریتم ساده اما طولانی این است که همانند روشی که برای دو لیست عمل کردیم، با شروع از ابتدای همه لیست‌ها، کمینه را پیدا کرده و آن را به آرایهٔ جواب اضافه نموده و این عمل تا زمانی که کل لیست‌ها خالی شوند، تکرار می‌کنیم. زمان اجرای این الگوریتم، ${\displaystyle O(nk)}$

الگوریتم دوم

در این الگوریتم، ابتدا لیست اول را با لیست دوم ادغام می‌کنیم، سپس حاصل را با لیست سوم ادغام می‌کنیم و همین گونه ادامه می‌دهیم تا به یک لیست نهایی برسیم. چون زمان اجرای ادغام دو لیست با ${\displaystyle n}$

${\displaystyle (k-1)\frac{n}{k}+(k-1)\frac{n}{k}+(k-2)\frac{n}{k}...+\frac{n}{k}=\frac{k(k-1)}{2}\times \frac{n}{k}+(k-1)\frac{n}{k}=O(nk)}$

در محاسبه زمان فرض شده‌است تعداد اعضای همهٔ لیست‌ها برابر و تعداد کل اعضا ${\displaystyle n}$

الگوریتم سوم

برای سریع‌تر انجام دادن این عملیات، از هرم کمینه استفاده می‌کنیم. ابتدا با استفاده از عضو اول همهٔ لیست‌ها، یک هرم کمینه می‌سازیم. این عمل می‌تواند در زمان اجرای ${\displaystyle O(n)}$

الگوریتم زیر در زبان پایتون چگونگی این ادغام را نشان می‌دهد. ورودی‌های این تابع، دو آرایهٔ مرتب ${\displaystyle A}$

def parallel_merge(A, B, C):
    if len(A) <len(B):
        A, B = B, A #make sure that A is the bigger Array
    if len(A) == 0:
        return  #there is nothing to merge
    r = len(A) // 2
    s = Binary-search(A[r], B)
    t = r + s
    C[t] = A[r]
    # do in parallel
    merge(A[0:r], B[0:s], C[0:t])
    merge(A[r+1:len(A)], B[s+1:len(B)], C[t+1:len(C)])

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

کاربرد دیگر این الگوریتم در مرتب‌سازی شکیبانه است. این مرتب‌سازی که در واقع از یک بازی کارتی گرفته شده‌است، به این گونه عمل می‌کند: فرض کنید ${\displaystyle n}$

از این الگوریتم در مرتب‌سازی خارجی نیز استفاده می‌شود. از مرتب‌سازی خارجی برای مرتب کردن اطلاعات فایل‌ها هنگامی که حافظهٔ اصلی یا RAM محدود است، بهره می‌گیریم. این گونه عمل می‌کنیم که در هر مرحله مقداری از فایل که در حافظهٔ اصلی می‌تواند قرار گیرد را برداشته، توسط یک الگوریتم مرتب‌سازی، مرتب نموده و در حافظهٔ خارجی مثلاً Hard Drive قرار می‌دهیم. در نهایت بخش‌های مرتب‌شدهٔ فایل را باهم ادغام می‌کنیم.