حد پایین الگوریتم های مرتب سازی که در هر تکرار بیش از یک وارونگی رو حذف میکنن،(مثل MergerSort) در بدترین حالت "سقف لوگاریتم (!n)" یا همان nlogn-1.45n است و در حالت میانگین کف لوگاریتم !n یا همان nlogn-1.45nچرا وجود داره. مثلا Radix sort از درجه (O(nk هست که
الگوریتم هایی که در هرتکرار حداکثر یک وارونگی رو حذف کنن در بدترین حالت و حالت متوسط (n^2) هستن(مثل Exchange sort)
این به این معنیه که هیچ الگورییتم مرتب سازی با ویژگی بالا نمیتونید بسازید که در بدترین حالت و حالت متوسط از nlogn بهتر عمل کنه؛
اگه لیست به صورت صعودی مرتب شده باشه و توهم بخوای صعودی مرتب کنی؛ الگوریتم مرتب سازی درجی در n تکرار به جواب میرسه؛ یعنی از nlogn بهتر عمل میکنه.اما اگه از قبل به صورت نزولی مرتب شده باشه(بدترین حالت) در (n^2) تکرار به جواب میرسه ( مثل QuickSort)الگوریتمی وجود نداره که در بهترین حالت زمانی کمتر از nLOGn داشته باش
البته هیچوقت نمیتونین بگین که مثلا همیشه MergeSort بهتره،؛ چون بر اساس مقدار n مثلا n<=1000 ممکن است دیگری بهتر باشه.