====== مرتب‌سازی در زمان خطی ======

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

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

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

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

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