‎$n$‎ وزنه با وزن‌های مختلف به ما داده‌اند. می‌توانیم کل این وزنه‌ها را به دو مجموعه‌ی ‎$A$‎ و ‎$B$‎ افراز کنیم و به ‎«ماشین توازن‎» بدهیم. این ماشین به ما می‌گوید که هر عضو ‎$A$‎ از چند تا از اعضای ‎$B$‎ بزرگ‌تر است. یعنی خروجی این ماشین برای مقایسه‌ی ‎$A$‎ با ‎$B$‎، $|A|$ تا عدد بین ‎$0$‎ تا ‎$|B|$‎ است.

دقت کنید که ‎$A$‎ و ‎$B$‎ همواره یک افراز‎ برای کل وزنه‌ها محسوب می‌شوند. یعنی ‎$A$‎ و ‎$B$‎ اشتراکی ندارند و اجتماعشان برابر کل وزنه‌هاست.

با ‎${\cal O}(\log(n))$‎ بار استفاده از این ماشین وزنه‌ها را مرتب کنید.

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