با توجه به حد پایین تعداد مقایسهها هیچ الگوریتم مبتنی بر مقایسه که موفق به مرتبسازی عناصر با پیچیدگی زمانی از $\mathcal{o}(n \log n)$ بشود وجود ندارد.
اما الگوریتمهای مرتبسازی وجود دارد که به نام الگوریتم مرتبسازی غیرمقایسهای شناخته شدهاند. این الگوریتمها برای مرتبسازی فقط از مقایسهی دو عنصر استفاده نمیکنند.
پیچیدگی زمانی این الگوریتمها با اینکه تابع خطی از اندازهی ورودی نیست اما تابع خطی از جمع اندازهی ورودی و اندازهی دامنهی عناصری است که توسط الگوریتم مرتب میشوند، به همین دلیل به آنها مرتبسازی خطی نیز گفته میشود.
برای مثال فرض کنید $n$ عدد صحیح مثبت دارید که هر کدام کوچکتر و یا مساوی $m$ هستند. بنابراین اندازهی دامنهی عناصر برابر $m$ است. پیچیدگی زمانی این مرتبسازیها تابعی خطی بر اساس $n$ و $m$ خواهد بود.
از الگوریتمهای غیرمقایسهای شناخته شده میتوان به مرتبسازی شمارشی، مرتبسازی رقمی و مرتبسازی سطلی اشاره کرد.