. متن داده‌شده را خلاصه کن

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