حد پایین تعداد مقایسه ها

تمام الگوریتم‌های بر پایه مقایسه، دارای حالتی از آرایه ورودی هستند که برای آن از مرتبه زمانی $\mathcal{\Omega}(n \log n)$ کار می‌کنند.

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