با توجه به حد پایین تعداد مقایسه‌ها هیچ الگوریتم مبتنی بر مقایسه که موفق به مرتب‌سازی عناصر با پیچیدگی زمانی کمتر از $n lg n$ بشود وجود ندارد.

اما الگوریتم‌های مرتب‌سازی وجود دارد که به نام الگوریتم مرتب‌سازی غیرمقایسه‌ای شناخته شده‌اند. این الگوریتم‌ها برای مرتب‌سازی از مقایسه‌ی دو عنصر استفاده نمی‌کنند.

پیچیدگی زمانی این الگوریتم‌ها با این‌که تابع خطی از اندازه‌ی ورودی نیست اما تابع خطی از اندازه‌ی دامنه‌ی عناصری است که توسط الگوریتم مرتب می‌شوند و به همین دلیل به آن‌ها مرتب‌سازی خطی نیز گفته می‌شود.

برای مثال فرض کنید $n$ عدد صحیح مثبت دارید که هر کدام کوچک‌تر و یا مساوی ‌$m$ هستند. بنابراین اندازه‌ی دامنه‌ی عناصر برابر $m$ است. پیچیدگی زمانی این مرتب‌سازی‌ها تابعی خطی بر اساس $n$ و $m$ خواهد بود.

از الگوریتم‌های غیرمقایسه‌ای شناخته شده می‌توان به مرتب‌سازی شمارشی، مرتب‌سازی رقمی و مرتب‌سازی سطلی اشاره کرد.