تحلیل الگوریتم ها:

• با استفاده از استقرای ریاضی نشان دهید زمانی که n توان صحیحی از ۲ است جواب رابطه بازگشتی زیر برابر چیست؟
• اگر n = 2 2
• اگر برای k>1 ، n = 2 T(n) = 2T(n/2) + n
• مرتب سازی درجی می تواند به صورت یک روال بازگشتی بشرح زیر بیان شود. به منظور مرتب کردن A[1..n]، آرایه A[1…n-1] را بطور بازگشتی مرتب کرده و سپس A(n) را د رآرایه مرتب شده A[1..n-1] درج می کنیم. یک رابطه بازگشتی برای زمان اجرای این نسخه بازگشتی از مرتب سازی درجی بنویسید.

مرتب سازی درجی روی آرایه های کوچک در مرتب سازی ادغام:

یک تغییر در مرتب سازی ادغام را در نظر بگیرید که درآن n/k زیر لیست با طول k با استفاده از مرتب سازی درجی، مرتب شده و سپس با استفاده از فرایند ادغام استاندارد ادغام می شوند و k مقداری است که باید مشخص شود:

1. نشان دهید که n/k زیر لیست هر یک با طول k می توانند بوسیله مرتب سازی درجی در بدترین حالت در زمان Θ(n/k) مرتب شوند.
2. نشان دهید که زیر لیست ها می توانند دربدترین حالت درزمان Θ(nlg(n/k)) ادغام شوند.

وارونگی:

1. چه آرایه ای با عناصر مجموعه {۱,۲,…,n } بیشترین وارونگی ها را دارد؟ این آرایه چند وارونگی دارد؟
2. چه رابطه ای بین زمان اجرای مرتب سازی درجی و تعداد وارونگی ها درآرایه ورودی وجود دارد؟
3. الگوریتمی ارائه دهید که تعداد وارونگی ها در یک جایگشت روی n عنصر را در بدترین حالت در زمان Θ(nlgn) تعیین کند.