====== مرتب‌سازی ======


یک جایگشت از اعداد ۱ تا $n$ داریم و هدف مرتب‌سازی آن در کم‌ترین تعداد حرکت است. در هر حرکت می‌توانیم یک زیردنباله از آن را انتخاب کنیم و با حفظ ترتیب به ابتدای جایگشت انتقال دهیم. به عنوان مثال این حرکت را در نظر بگیرید:

$$12\underline{4}53\underline{76} \longrightarrow \underline{476}1253$$

نشان دهید هر جایگشت $n$ تایی را می‌توان با حداکثر $lg(n+1)$ حرکت مرتب کرد.


  * [[سوال ۲|سوال بعد]]