موضوع مقاله: مرتب‌سازی ادغام-درج | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مرتب‌سازی ادغام-درج | مقدمه: در علوم رایانه، مرتب‌سازی ادغام-درج یا الگوریتم فورد-جانسون از الگوریتم‌های مرتب‌سازی مقایسه‌ای است که در سال ۱۹۵۹ توسط لستر رادولف فورد و سلمر مارتین جانسون منتشر شد. | ## بخش 1: مرتب‌سازی ادغام-درج | این الگوریتم از الگوریتم‌های شناخته شده قبلی همچون مرتب‌سازی درجی دودویی و مرتب‌سازی ادغامی در بدترین حالت، از تعداد مقایسه‌های کمتری استفاده می‌کند. مقدمه ای بر الگوریتم فرض می‌کنیم ۵ عدد داریم ، آن‌ها را به سه دسته تقسیم می‌کنیم: سپس دو عدد موجود در دسته‌های دوتایی را باهم مقایسه می‌کنیم و بعد از آن دو عدد بزرگتر هر دسته را با یکدیگر مقایسه می‌کنیم. در شکل‌های زیر جهت پیکان از عدد کوچکتر به سمت عدد بزرگتر است.وسط وسط|بی‌قاب با توجه به شکل بالا داریم . اکنون باید عنصر را بین این سه عنصر مرتب شده درج کنیم که با دو مقایسه امکان‌پذیر است. (مرتب‌سازی درجی دودویی) سپس بعد از معلوم شدن جایگاه ، عنصر را در صف مرتب شده درج می‌کنیم که آن نیز با دو مقایسه امکان‌پذیر است. الگوریتم الگوریتم فورد-جانسون یا مرتب‌سازی ادغام-درج تعمیم جالبی از مقدمه بالاست. ادغام عنصر موجود را به گروه دوتایی تقسیم می‌کنیم؛ و اگر فرد بود، یک عنصر جفت نشده باقی می‌ماند. | ## بخش 2: مرتب‌سازی ادغام-درج | حال عناصر مرتب شده را زنجیره اصلی می‌نامیم که به صورت در شکل نمایش داده شده‌است. وسط|بی‌قاب|413x413پیکسل سپس با توجه به این که زنجیره اصلی مرتب شده‌است و عنصر کوچکترین عنصر زنجیره است و می‌دانیم از آن کوچکتر است، بنابراین می‌توان را در ابتدای زنجیره درج نمود. (با استفاده از مرتب‌سازی درجی) درج روش درج کردن ها به ترتیب زیر است: سپس در آخر در صورت وجود، را در زنجیره اصلی درج می‌نماییم. این مقادیر باید باید به گونه‌ای باشند که تعداد عناصر زنجیره اصلی هنگام درج یک عنصر در مرحله ام برابر باشد. در نتیجه داریم: با حل رابطه بازگشتی بالا به جواب زیر می‌رسیم: را تعداد مقایسه‌های الگوریتم فورد-جانسون برای عنصر می‌گیریم. ابتدا مقایسه برای پیدا کردن عنصر بزرگتر در هر دسته داریم و سپس زنجیره اصلی را به شکل بازگشتی مرتب می‌کنیم و هم تعداد مقایسه‌ها برای درج عناصر کوچکتر دسته‌ها در زنجیره اصلی است. پس از تعریف به شکل بالا می‌توان ثابت کرد : و شرط بالا معادل است با : بنابرابن داریم : در نتیجه: مقایسه با سایر الگوریتم‌ها نام این الگوریتم ادغام-درج است زیرا مقایسه‌های اولیه که قبل از فراخوانی بازگشتی انجام می‌شود، همچون مقایسه‌های الگوریتم مرتب‌سازی ادغامی است و همچنین مقایسه‌هایی که بعد از فراخوانی بازگشتی صورت می‌گیرد، مانند الگوریتم مرتب‌سازی درجی دودویی است. | ## بخش 3: مرتب‌سازی ادغام-درج | در واقع می‌توان الگوریتم فورد-جانسون را الگوریتم چندگانه نامید زیرا تلفیقی از دو مرتب‌سازی درجی و ادغامی است. تعداد مقایسه‌های این الگوریتم مرتب‌سازی برای برابر با کران پایین تعداد مقایسه‌های مرتب‌سازی‌های مقایسه‌ای است. این کران پایین برابر است با امّا تعداد مقایسه برای های بزرگتر بیشتر از این کران پایین است. همان‌طور که در جدول زیر دیده می‌شود، تعداد مقایسه‌ها در الگوریتم فورد-جانسون از دو الگوریتم ادغامی و درجی برای های کوچکتر از کمتر است. +تعداد مقایسه‌ها در بدترین حالت۱۷۱۶۱۵۱۴۱۳۱۲۱۱۱۰۹۸۷۶۵۴۳۲۱n۵۴۴۹۴۵۴۱۳۷۳۳۲۹۲۵۲۱۱۷۱۴۱۱۸۵۳۱۰مرتب‌سازی درجی۶۵۴۹۴۵۴۱۳۸۳۳۳۰۲۷۲۵۱۷۱۴۱۱۹۵۳۱۰مرتب‌سازی ادغامی۵۰۴۶۴۲۳۸۳۴۳۰۲۶۲۲۱۹۱۶۱۳۱۰۷۵۳۱۰مرتب‌سازی ادغام-درج الگوریتم‌های بهینه تر تا به امروز الگوریتم بهینه‌تر از نظر زمانی برای الگوریتم فورد-جانسون ارائه شده‌است که تعداد مقایسه‌های دقیقاً برابر فورد-جانسون است؛ امَا زمان کمتری می‌گیرد بدین گونه که به جای فراخوانی بازگشتی بر روی نصف لیست اعداد، بر روی یک چهارم لیست اعداد می‌باشد. تا بیست سال الگوریتم فورد-جانسون، کمترین تعداد مقایسه را میان الگوریتم‌های مرتب‌سازی داشت. در سال ۱۹۷۹ گلن ماناکر الگوریتم مرتب‌سازی دیگری ارائه کرد که تعداد مقایسه‌های آن از فورد-جانسون حتی برای ورودی‌ها با تعداد زیاد نیز کمتر بود. | ## جمع‌بندی | امروزه الگوریتمی ارائه شده‌است که به نتایج قوی‌تری نسبت به الگوریتم ماناکر دست یافته‌است.