مرتب‌سازی ادغام-درج

در علوم رایانه، **مرتب‌سازی ادغام-درج** یا الگوریتم فورد-جانسون از الگوریتم‌های مرتب‌سازی مقایسه‌ای است که در سال ۱۹۵۹ توسط لستر رادولف فورد و سلمر مارتین جانسون منتشر شد. این الگوریتم از الگوریتم‌های شناخته شده قبلی همچون مرتب‌سازی درجی دودویی و مرتب‌سازی ادغامی در بدترین حالت، از تعداد مقایسه‌های کمتری استفاده می‌کند.

مشخص است که کم بودن تعداد مقایسه‌ها معیاری مناسب برای اثربخشی یک الگوریتم مرتب‌سازی نیست؛ امّا از دیدگاه نظری کمینه کردن تعداد مقایسه‌ها در مسائل مرتب‌سازی همواره مهم بوده‌است. همین الگوریتم توسط ریاضیدان لهستانی به‌طور مستقل کشف شد.

## مقدمه ای بر الگوریتم
فرض می‌کنیم ۵ عدد داریم (a,b,c,d,e)، آن‌ها را به سه دسته تقسیم می‌کنیم: (a,b) (c,d) (e)

سپس دو عدد موجود در دسته‌های دوتایی را باهم مقایسه می‌کنیم و بعد از آن دو عدد بزرگتر هر دسته را با یکدیگر مقایسه می‌کنیم. فرض می‌کنیم a>b , c>d. آنگاه باید دو عدد a,c را با هم مقایسه کنیم. در شکل‌های زیر جهت پیکان از عدد کوچکتر به سمت عدد بزرگتر است.وسط
وسط|بی‌قاب
با توجه به شکل بالا داریم b. اکنون باید عنصر e را بین این سه عنصر مرتب شده درج کنیم که با دو مقایسه امکان‌پذیر است. (مرتب‌سازی درجی دودویی) سپس بعد از معلوم شدن جایگاه e، عنصر d را در صف مرتب شده درج می‌کنیم که آن نیز با دو مقایسه امکان‌پذیر است.

## الگوریتم
الگوریتم فورد-جانسون یا مرتب‌سازی ادغام-درج تعمیم جالبی از مقدمه بالاست. مراحل این الگوریتم به شرح زیر است:

### ادغام
# n عنصر موجود را به \left \lfloor \frac{n}{2} \right \rfloor گروه دوتایی تقسیم می‌کنیم؛ و اگر n فرد بود، یک عنصر جفت نشده باقی می‌ماند.
# \left \lfloor \frac{n}{2} \right \rfloorمقایسه انجام می‌دهیم تا عنصر بزرگتر در هر گروه را بیابیم.
# \left \lfloor \frac{n}{2} \right \rfloor عنصر بزرگتر را به شکل بازگشتی مرتب می‌کنیم. حال عناصر مرتب شده را زنجیره اصلی می‌نامیم که به صورت a_iدر شکل نمایش داده شده‌است. وسط|بی‌قاب|413x413پیکسل
# سپس با توجه به این که زنجیره اصلی مرتب شده‌است و عنصر a_1
 کوچکترین عنصر زنجیره است و می‌دانیم b_1 از آن کوچکتر است، بنابراین می‌توان b_1 را در ابتدای زنجیره درج نمود.
# بقیه عناصر که به شکل b_i
 نشان داده شده‌است را در زنجیره اصلی درج می‌کنیم. (با استفاده از مرتب‌سازی درجی)

### درج
روش درج کردن b_i
ها به ترتیب زیر است:

b_3 ,b_2; b_5,b_4; b_11,b_10,...,b_6;.....;b_{t_k},b_{t_{k-1}},......,b_{t_{k-1}}+1


(t_1,t_2,t_3,t_4,...)=(1,3,5,11,...)

سپس در آخر در صورت وجود، b_{3} 

بنابرابن داریم : F(n)-F(n-1)=\left \lceil log(\frac{3}{4}n )\right \rceil


در نتیجه: F(n)=\sum_{k=1}^n\left \lceil log(\frac{3}{4}k )\right \rceil


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

تعداد مقایسه‌های این الگوریتم مرتب‌سازی برای n\leq 11برابر با کران پایین تعداد مقایسه‌های مرتب‌سازی‌های مقایسه‌ای است. این کران پایین برابر است با \lceil\log_2 n!\rceil\approx n\log_2 n -  1.443n

امّا تعداد مقایسه برای n
های بزرگتر بیشتر از این کران پایین است.

همان‌طور که در جدول زیر دیده می‌شود، تعداد مقایسه‌ها در الگوریتم فورد-جانسون از دو الگوریتم ادغامی و درجی برای n
های کوچکتر از 18
 کمتر است.

## الگوریتم‌های بهینه تر
تا به امروز الگوریتم بهینه‌تر از نظر زمانی برای الگوریتم فورد-جانسون ارائه شده‌است که تعداد مقایسه‌های دقیقاً برابر فورد-جانسون است؛ امَا زمان کمتری می‌گیرد بدین گونه که به جای فراخوانی بازگشتی بر روی نصف لیست اعداد، بر روی یک چهارم لیست اعداد می‌باشد.

تا بیست سال الگوریتم فورد-جانسون، کمترین تعداد مقایسه را میان الگوریتم‌های مرتب‌سازی داشت. در سال ۱۹۷۹ گلن ماناکر الگوریتم مرتب‌سازی دیگری ارائه کرد که تعداد مقایسه‌های آن از فورد-جانسون حتی برای ورودی‌ها با تعداد زیاد نیز کمتر بود.

ماناکر نشان داد الگوریتم فورد-جانسون برای محدوده‌ای از مقادیر بهینه است. امروزه الگوریتمی ارائه شده‌است که به نتایج قوی‌تری نسبت به الگوریتم ماناکر دست یافته‌است.

## منابع

رده:مرتب‌سازی‌های سنجشی
رده:علوم رایانه در ۱۹۵۹ (میلادی)