تابع $Q(A)$ (که $A[1..n]$ آرایه‌ای از اعداد غیرتکراری است) یک جایگشت $\pi$ از اعداد ۱ تا $n$ را برمی‌گرداند بدین صورت که $\pi_i = b(A[i],A)$ که $b(x,A)$ برابر است با تعداد اعداد کوچکترمساوی $x$ در $A$.

تابع $R(\pi,S)$ که $\pi$ یک جایگشت و $S\subset\{1,\dots,n\}$ آرایه‌ی $A[1..n]$ را برمی‌گرداند که $A[i]=\pi_i - n$ برای $i \in S$ و $A[i] = \pi_i$ برای $i \notin S$.

می‌خواهیم با اجرای توابع $Q$ و $R$ بر روی یک جایگشت $\pi$ آن را مرتب کنیم. ثابت کنید با $\left\lceil{\log_2(n)}\right\rceil$ بار استفاده از $R$ می‌توان هر جایگشتی را مرتب کرد.

راهنمایی: وارون جایگشت را در نظر بگیرید.