الترتيب بالمقارنة
عدد المقارنات المطلوبة لترتيب عناصر قائمة

| n |  \left\lceil \log _{2}(n!)\right\rceil  | الحد الأدنى |
| --- | --- | --- |
1: 0
2: 1
3: 3
4: 5
5: 7
6: 10
7: 13
8: 16
9: 19
10: 22
11: 26
| 12 | 29 | 30  |
| 13 | 33 | 34  |
| 14 | 37 | 38  |
| 15 | 41 | 42  |
| 16 | 45 | 45 أو 46  |
| 17 | 49 | 49 أو 50 |
| 18 | 53 | 53 أو 54 |
| 19 | 57 | 58  |
20: 62
21: 66
| 22 | 70 | 71  |
------ الجزء الثاني-------: ------ الجزء الثاني-------
| n |  \left\lceil \log _{2}(n!)\right\rceil  |  n\log _{2}n-{\frac {n}{\ln 2}} |
| 10 | 22 | 19 |
| 100 | 525 | 521 |
| 1000 | 8530 | 8524 |
| 10000 | 118,459 | 118,451 |
| 100000 | 1,516,705 | 1,516,695 |
| 1,000,000 | 18,488,885 | 18,488,874 |
الجزء الأول: مقارنة بين الحد الأدنى لعدد المقارنات باستخدام المعادلة التالية:  \left\lceil \log _{2}(n!)\right\rceil ، والعدد الأدنى الفعلي (المصدر:OEIS:A036604) لعدد المقارنات المطلوبة لترتيب قائمة مكونة من n من العناصر (في أسوأ حالة).  الجزء الثاني من الجدول قرب الحد الأدنى لعدد المقارنات المطلوبة باستخدام تقريب ستيرلنغ تقريبا جيدا باستخدام المعادلة التالية: n\log _{2}n-{\frac {n}{\ln 2}}: الجزء الأول: مقارنة بين الحد الأدنى لعدد المقارنات باستخدام المعادلة التالية:  \left\lceil \log _{2}(n!)\right\rceil ، والعدد الأدنى الفعلي (المصدر:OEIS:A036604) لعدد المقارنات المطلوبة لترتيب قائمة مكونة من n من العناصر (في أسوأ حالة).  الجزء الثاني من الجدول قرب الحد الأدنى لعدد المقارنات المطلوبة باستخدام تقريب ستيرلنغ تقريبا جيدا باستخدام المعادلة التالية: n\log _{2}n-{\frac {n}{\ln 2}}
مثال: إذا كانت n=10 , فإن الحد الأدنى يساوي 22, والحد الأدنى الفعلي يساوي أيضا 22, بينما باستخدام تقريب ستيرلينغ، فإن الحد الأدنى (مقرّب باستخدام المعادلة) يساوي 19.عدد المقارنات التي تتطلبها خوارزميات الترتيب بالمقارنة تزداد بالتناسب مع  n\log(n)، حيث أن  n هو عدد العناصر المطلوب ترتيبها. هذا الحد هو حد محكم بشكل مقارب.
إذا كان لدينا مجموعة من الأعداد المختلفة (يمكننا افتراض هذا الإختلاف لأن هذا الإختلاف هو تحليل لأسوأ حالة)، فهناك عدد من البدائل يساوي مضروب حجم القائمة (! n)، واحد منها فقط يمثل القائمة بالترتيب المطلوب.
مثال: لو كان هناك قائمة مكونة من ثلاثة عناصر n=3 وقيمها {1,2,3}، فإن عدد البدائل يساوي !3 ويساوي 6 بدائل، هذه البدائل هي: {1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,2,1} {3,1,2}.
يجب أن تحصل خوارزمية الترتيب على معلومات كافية من عمليات المقارنات لتحديد البديل الصحيح. إذا كانت الخوارزمية تنهي عملها دائمًا بعد  f(n) من الخطوات على الأكثر، فإنه لا يمكن لها تمييز أكثر من  2^{f(n)} من الحالات لأن العناصر جميعها مميزة ولأن كل مقارنة لها نتيجتين محتملتين فقط. وبالتالي:
بالنظر إلى أول  n/2 من عوامل (! n)
n!=n(n-1)\cdots 1 نحصل على:
\log _{2}(n!)\geq \log _{2}\left(\left({\frac {n}{2}}\right)^{\frac {n}{2}}\right)={\frac {n}{2}}{\frac {\log n}{\log 2}}-{\frac {n}{2}}=\Theta (n\log n).
هذا يؤدي إلى جزئية الحد الأدنى من الفرضية. يمكن إعطاء حد أفضل من خلال تقريب ستيرلنغ.
حد أعلى مطابق للحد الأدنى أعلاه يأتي من وجود الخوارزميات التي تحقق هذا الحد في أسوأ الحالات، مثل خوارزميتي ترتيب الدمج وترتيب الكومة. النقاش أعلاه يعطي حدًا أدنى مطلقًا، وليس فقط حدًا مقاربًا، لعدد المقارنات، تحديدا  \left\lceil \log _{2}(n!)\right\rceil  من المقارنات. هذا الحد الأدنى جيد إلى حد مقبول (يمكن الوصول إليه بتفاوت خطي من خلال خوارزمية ترتيب الدمج)، ولكن من المعروف أنه غير دقيق. فمثلا،
\left\lceil \log _{2}(13!)\right\rceil =33
علما بأنه أقل عدد مثبت من المقارنات لترتيب 13 عنصرًا هو 34 عملية مقارنة.
إن تحديد العدد الفعلي للمقارنات اللازمة لترتيب عدد معين من العناصر هي مشكلة حسابية صعبة حتى بالنسبة لـعدد قليل من العناصر n، ولا توجد صيغة رياضية بسيطة معروفة للحل. للإطلاع على بعض القيم التي تم حسابها، انظر إلى OEIS:A036604.