یک دنباله به طول ‎$n$‎ از اعداد متفاوت به ما داده‌اند و ما می‌خواهیم این دنباله را مرتب کنیم. مجاز به عوض کردن جای عناصر مختلف این دنباله هستیم اما از آن‌جا که روی هر کدام از این اعداد یک کارت قرار داده‌اند از مقدار این اعداد آگاهی نداریم. فقط به ما یک ماشین داده‌اند که به عنوان ورودی اندیس ‎$k$‎ تا از عناصر دنباله را دریافت می‌کند و به ما می‌گوید ترتیب مرتب‌شده‌ی این ‎$k$‎ عنصر نسبت به هم چگونه است. دقت کنید که ماشین ترتیب عناصر درون دنباله را عوض نمی‌کند، بلکه فقط به شما اطلاعات می‌دهد. این شما هستید که باید بر اساس این اطلاعات دنباله را مرتب کنید.

1. در صورتی که این ‎$k$‎ عنصر فقط بتوانند ‎$k$‎ عنصر متوالی باشند، الگوریتمی ارائه کنید که با ‎$O((n/k)^2)$‎ استفاده از این ماشین، دنباله را مرتب کند.
2. در صورتی که این ‎$k$‎ عنصر بتوانند هر ‎$k$‎ عنصر دلخواهی باشند، الگوریتمی ارائه کنید که با ‎$O(n\log(n)/k)$‎ استفاده از این ماشین، دنباله را مرتب کند.

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