یک نفر از الگوریتم $MergeSort$ فقط قسمت $Merge$ آن را بلد است. او برای مرتب کردن آرایه‌ای از $2n$ عدد مثل $A[1...2n]$ همواره در هر مرحله آن را به دو قسمت مساوی $A_1=A[1...n]$ و $A_2=A[n+1...2n]$ تقسیم می‌کند و آن‌ها را به این صورت $Merge$ می‌کند که دو اشاره‌گر به ابتدای $A_1$ و $A_2$ قرار می‌دهد و هر بار عناصر مورد اشاره را با هم مقایسه می‌کند و عنصر کوچک‌تر را به ترتیب در آرایه‌ای مثل $B$ که در ابتدای کار خالی شده است می‌نویسد و اشاره‌گر مربوط به عدد نوشته شده را یکی جلو می‌برد (همان $Merge$ خودمان) و در انتهای مرحله، آرایه‌ی $B$ را در $A$ می‌نویسد.

او این مراحل را آن‌قدر تکرار می‌کند تا $A$ مرتب شود. مثلا $[2,4,3,1]$ در دو مرحله به ترتیب تبدیل به $[2,3,1,4]$ و $[1,2,3,4]$ که مرتب شده است.

الف) به ازای هر $n$ مثالی از یک مقداردهی برای $A$ بدهید که هیچ وقت مرتب نشود.

ب) نشان دهید اگر اعداد داخل $A$ متفاوت باشند و اگر قرار باشد که $A$ مرتب شود، حداکثر در $O(nH_n)$ مرحله مرتب می‌شود. $(H_n=\sum_{i=1}^n \frac{1}{i})$

• سوال بعد
• سوال قبل