====== مرتب کن ======

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

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

با ‎${\cal O}(\log(n))$‎ بار استفاده از این ماشین وزنه‌ها را مرتب کنید. 
  * [[سوال ۱۶|سوال بعد]]
  * [[سوال ۱۴|سوال قبل]]