برای مرتب‌سازی یک آرایه، پیش‌نهاد شده است که به شکل بازگشتی ابتدا دوسوم اول آرایه را مرتب کنیم، سپس دوسوم دوم آرایه را و بعد مجددا دوسوم اول را.

الف) رویه‌ی کاملی بنویسید که با استفاده از روش فوق آرایه‌ی $n$ تایی $A$ را که شامل این اعداد است، مرتب کند.(نیازی به نوشتن بخش‌های ورودی / خروجی نیست.)

ب) ثابت کنید الگوریتم فوق همواره درست عمل می‌کند.

ج) این الگورریتم را از نظر زمانی تحلیل کنید و مرتبه‌ی دقیق $(\Theta)$ آن را در بد‌ترین حالت به‌دست آورید.

• سوال بعد