الگوریتم مرتب‌سازی
همسنجی سریع

جدول زیر مربوط به الگوریتم‌های تطبیقی است. به کمک درخت تصمیم می‌توان ثابت کرد حداقل زمان مرتب‌سازی با روش مقایسه در حالت میانگین،  O(nlogn)\! می‌باشد.
| نام | میانگین | بدترین | حافظه | پایداری | روش | نکات اضافه |
| --- | --- | --- | --- | --- | --- | --- |
| مرتب‌سازی حبابی |  {\mathcal {}}n^{2} |  {\mathcal {}}n^{2} |  {\mathcal {}}{1} | بله | تعویض | کد کوتاه |
| مرتب‌سازی حبابی دوسویه | — |  {\mathcal {}}n^{2} |  {\mathcal {}}{1} | بله | تعویض |  |
| مرتب‌سازی شانه‌ای | — | — |  {\mathcal {}}{1} | خیر | تعویض | کد کوتاه |
| مرتب‌سازی گورزاد | — |  {\mathcal {}}n^{2} |  {\mathcal {}}{1} | بله | تعویض | کد کوتاه |
| مرتب‌سازی انتخابی |  {\mathcal {}}n^{2} |  {\mathcal {}}n^{2} |  {\mathcal {}}{1} | بستگی دارد | انتخاب | پایدار بودن آن به پیاده‌سازی بستگی دارد |
| مرتب‌سازی درجی |  {\mathcal {}}n^{2} |  {\mathcal {}}n^{2} |  {\mathcal {}}{1} | بله | درج | حالت میانگین همچنین  {\mathcal {O}}\left({n+d}\right) می‌باشد که d تعداد درج‌هاست. |
| مرتب‌سازی شل | — |  {\mathcal {}}{n\log ^{2}n} |  {\mathcal {}}{1} | خیر | درج |  |
| مرتب‌سازی درختی |  {\mathcal {}}{n\log n} |  {\mathcal {}}{n\log n} |  {\mathcal {}}n | بله | درج | باید از یک درخت دودویی جستجوگر خود متوازن استفاده شود |
| مرتب‌سازی کتابخانه‌ای |  {\mathcal {}}{n\log n} |  {\mathcal {}}n^{2} |  {\mathcal {}}n | بله | درج |  |
| مرتب‌سازی ادغامی |  {\mathcal {}}{n\log n} |  {\mathcal {}}{n\log n} |  {\mathcal {}}n | بله | ادغام |  |
| مرتب‌سازی ادغامی درجا |  {\mathcal {}}{n\log n} |  {\mathcal {}}{n\log n} |  {\mathcal {}}{1} | بستگی دارد | ادغام | نمونه پیاده‌سازی اینجا: ؛ می‌تواند به عنوان یک مرتب‌سازی پایدار پیاده‌سازی شود:  |
| مرتب‌سازی هرمی |  {\mathcal {}}{n\log n} |  {\mathcal {}}{n\log n} |  {\mathcal {}}{1} | خیر | انتخاب |  |
| مرتب‌سازی روان | — |  {\mathcal {}}{n\log n} |  {\mathcal {}}{1} | خیر | انتخاب |  |
| مرتب‌سازی سریع |  {\mathcal {O}}\left({n\log n}\right) |  {\mathcal {O}}\left(n^{2}\right) |  {\mathcal {O}}\left({\log n}\right) | بستگی دارد | تقسیم‌بندی | با توجه به شیوه‌ای که محور عمل می‌کند، می‌تواند به صورت پایدار پیاده‌سازی شود؛ گونهٔ دیگری از آن از حافظه  {\mathcal {O}}\left(n\right) استفاده می‌کند. |
| مرتب‌سازی درونگرا |  {\mathcal {O}}\left({n\log n}\right) |  {\mathcal {O}}\left({n\log n}\right) |  {\mathcal {O}}\left({\log n}\right) | خیر | مرکب | استفاده شده در پیاده‌سازی‌های SGI STL |
| مرتب‌سازی شکیبانه | — |  {\mathcal {O}}\left({n\log n}\right) |  {\mathcal {O}}\left(n\right) | خیر | درج و انتخاب | بزرگ‌ترین زیر‌دنباله‌های افزایشی را با  O(nlogn)\! پیدا می‌کند. |
| مرتب‌سازی رشته‌ای |  {\mathcal {O}}\left({n\log n}\right) |  {\mathcal {O}}\left({n^{2}}\right) |  {\mathcal {O}}\left(n\right) | بله | انتخاب |  |
| مرتب‌سازی مسابقه‌ای |  {\mathcal {O}}\left({n\log n}\right) |  {\mathcal {O}}\left({n\log n}\right) |  |  | انتخاب |  |
جدول زیر مربوط به الگوریتم‌های ناتطبیقی است. این الگوریتم‌ها محدودیت  O(nlogn)\! الگوریتم‌های تطبیقی را ندارند.  k اندازه کلیدها و  s مقداری است که در پیاده‌سازی استفاده شده‌است. خیلی از این الگوریتم‌ها بر این فرض استوارند که سایز کلیدها به قدری بزرگ است که همهٔ کلیدها مقدار یکسانی دارند. و  <<\! یعنی "خیلی کمتر از".
| نام | میانگین | بدترین | حافظه | پایداری | n << 2k | نکات دیگر |
| --- | --- | --- | --- | --- | --- | --- |
| مرتب‌سازی لانه‌کبوتری |  {\mathcal {O}}\left({n+2^{k}}\right) |  {\mathcal {O}}\left({n+2^{k}}\right) |  {\mathcal {O}}\left({2^{k}}\right) | بله | بله |  |
| مرتب‌سازی سطلی |  {\mathcal {O}}\left({n\cdot k}\right) |  {\mathcal {O}}\left({n^{2}\cdot k}\right) |  {\mathcal {O}}\left({n\cdot k}\right) | بله | خیر | فرض می‌کند عناصر در محدودهٔ خود یکنواخت پخش شده‌اند. |
| مرتب‌سازی شمارشی |  {\mathcal {O}}\left({n+k}\right) |  {\mathcal {O}}\left({n+k}\right) |  {\mathcal {O}}\left({n+2^{k}}\right) | بله | بله | اگر k =  {\mathcal {O}}\left({n}\right) آنگاه میانگین =  {\mathcal {O}}\left({n}\right) |
| مرتب‌سازی مبنایی کم ارزش‌ترین رقم |  {\mathcal {O}}\left({n\cdot {\frac {k}{s}}}\right) |  {\mathcal {O}}\left({n\cdot {\frac {k}{s}}}\right) |  {\mathcal {O}}\left(n\right) | بله | خیر |  |
| مرتب‌سازی مبنایی پرارزش‌ترین رقم |  {\mathcal {O}}\left({n\cdot {\frac {k}{s}}}\right) |  {\mathcal {O}}\left({n\cdot {\frac {k}{s}}\cdot 2^{s}}\right) |  {\mathcal {O}}\left({{\frac {k}{s}}\cdot 2^{s}}\right) | خیر | خیر |  |
| مرتب‌سازی گسترده |  {\mathcal {O}}\left({n\cdot {\frac {k}{s}}}\right) |  {\mathcal {O}}\left({n\cdot \left({{\frac {k}{s}}+s}\right)}\right) |  {\mathcal {O}}\left({{\frac {k}{s}}\cdot 2^{s}}\right) | خیر | خیر |  |