تمام الگوریتم هایی که بر پایه مقایسه آرایه ای را مرتب می کنند دارای مرتبه زمانی $\Omega(n lg n)$ هستند.

در یک الگوریتم مرتب سازی بر پایه مقایسه بعد از مقایسه دو عنصر مانند $a$ و $b$ دو جواب مختلف بدست می آوریم (فرض کنید $a \ne b$). پس اگر قبل این مقایسه آرایه نهایی ما $x$ جایگشت مختلف از ورودی می توانست داشته باشد، بعد از مقایسه در یکی از حالت های جواب مقایسه، $y$ جایگشت مختلف از ورودی و در حالت دیگر $x-y$ حالت مختلف از ورودی می تواند داشته باشد. با توجه به اینکه حداقل یکی از دو مقدار $y$ و $x-y$ بزرگتر از $x ÷ 2$ است پس در یکی از حالت ها تعداد حالت های نهایی بعد از مقایسه بیش تر مساوی تعداد حالت های نهایی قبل از مقایسه است. یعنی اگر بدشانس باشیم بعد هر مقایسه تعداد حالات نهایی بیش تر از نصف تعداد حالات نهایی قبل مقایسه خواهد بود. حال با توجه به اینکه قبل از تمام مقایسه ها خروجی $n!$ جایگشت مختلف از ورودی را می تواند داشته باشد و در هر مرحله تعداد حالات بیش تر از نصف تعداد حالات در مرحله قبل است، حداقل به $(1 \le i \le n), lg (n!) = \Sigma lg (i)$ مقایسه نیاز داریم. یعنی تعداد مقایسه های ما دارای مرتبه زمانی $\Omega(n lg n)$ است.