مرتب‌سازی مقایسه‌ای
در علم کامپیوتر معمولاً الگوریتم‌های مرتب‌سازی بر اساس معیارهای مختلفی چون پیچیدگی زمانی، حافظه، پایداری و همسنجشی (مقایسه‌ای) بودن یا نبودن طبقه‌بندی می‌شوند. یک الگوریتم مرتب‌سازی همسنجشی (مقایسه‌ای)، الگوریتمی است که در هر مرحله بر حسب صلاح دید الگوریتم، دو خانه از یک آرایه را انتخاب می‌کند و آن دو را با هم می‌سنجد و در صورت نیاز درایه‌های آن‌ها را با هم عوض می‌کند. نحوهٔ عملکرد الگوریتم به صورت زیر است:
۱ اگر a≤b و b≤c آن گاه حتماً عدد a کوچکتر مساوی عدد c است.
۲ به ازای تمامی اعداد مثل a و b، رابطهٔ aمرتب‌سازی سریع
نمونه‌هایی از الگوریتم‌هایی که در آن‌ها مرتب‌سازی بر اساس همسنجی نیست، عبارتند از:
محدودیت‌های اساسی در الگوریتم‌های مرتب‌سازی همسنجشی وجود دارد. یک مرتب‌سازی مقایسه‌ای بایستی تعداد اعمال مقایسه اش از (Ω("n" log "n" فراتر نرود. مرتب‌سازی ادغامی، هرمی و intro از نظر تعداد اعمالی که برای مقایسه باید انجام دهند، در شرایط مطلوبی هستند. اگر چه این سنجه، عملیات دیگر را نادیده می‌گیرد. مرتب‌سازی مبنایی، شمارشی و سطلی عملکردی از مرتبه (O("n" هستند و عملیاتی جز مقایسه انجام می‌دهند. با این حال، مرتب‌سازی همسنجشی یک مزیت قابل توجه دارد و آن این است که عمل همسنجی برای مرتب‌سازی انواع داده قابل استفاده‌است. هم چنین می‌توان با برعکس کردن نتیجهٔ مرتب‌سازی، اعضای مرتب شده را به صورت معکوس روئیت کرد. برای مثال با استفاده از یک الگوریتم مقایسه‌ای می‌توان لیستی از تاپل‌هایی که به صورت lexicographic هستند را مرتب کرد:
مقایسه در یک مرحله انجام می‌شود و نتیجه اش یا 'بزرگتر است از'، 'یا کوچکتر است از' یا 'مساوی است'، به دست می‌آید.
تعداد مقایسه‌های لازم در الگوریتم‌های مرتب‌سازی مقایسه‌ای حداقل به نسبت formula_1 افزایش می‌یابد که n تعداد اعضای لیست است. برای تحلیل بدترین حالت صرف زمان در این نوع الگوریتم‌ها، فرض می‌کنیم لیستی از اعداد متمایز داریم و به تعداد !n جایگشت لازم است برای آن که لیست مرتب شود. اگر الگوریتم بعد از حداکثر ("f"("n" مرحله پایان پذیرد، نمی‌توان بیش تر از 2 مورد را تشخیص داد چرا که مقادیر متمایز هستند و نتیجه هر مقایسه دقیقاً دو حالت دارد. در نتیجه: formula_2 یا آن که formula_3
از طریق تقریب استرلینگ می‌دانیم:
formula_4 همان formula_5 است.
با استفاده از این موضوع حد پایین تحلیل زمانی به دست می‌آید. مشابه الگوریتم‌هایی که از این دست الگوریتم‌ها پیروی می‌کنند، حد بالای تحلیل زمانی در بدترین حالت به دست می‌آید. استدلال بالا یک تحلیل مطلق را به جای یک تحلیل مجانبی برای حد پایین بیان می‌کند. حد پایین تقریباً خوب است چرا که با استفاده از یک مرتب‌سازی ادغامی ساده در محدوده خطی قابل دستیابی است. اما این موضوع دقیق نیست؛ برای مثال برای آن که ۱۳ عنصر را مرتب کنیم، به ۳۴ مقایسه نیاز داریم.. مشخص کردن تعداد دقیق مقایسه‌ها برای یک سری ورودی‌های مشخص ولو با تعداد کم، کار پیچیده‌ای است و هیچ فرمول ساده‌ای برای این مسئله وجود ندارد. برای تعداد کمی از مقادیر محاسبه شده این پیوند را مشاهده کنید.
یک محدوده مشابه برای میانگین تعداد مقایسه‌ها به کار برده می‌شود. فرض کنیم: باید دقت داشت که این موضوع با بحث بدترین حالتی که پیش از این انجام شد، متفاوت است. در آن بحث اجازه گرد کردن اعداد به نزدیک ترین عدد صحیح را نداریم. برای مثال، به ازای n=۳، محدوده پایین برای بدترین حالت ۳ است، برای حالت میانگین تقریباً برابر با ۲٫۵۸ است. در صورتی که در حالت بالا این مقدار برابر با ۲٫۶۷ است. در حالتی که مقادیر مختلف برای کلید یکسان به دست بیاید، هیچ گونه تفسیر آماری برای «حالت میانگین» وجود ندارد؛ بنابراین بحثی که شد بدون در نظر گرفتن فرضیات دقیق ارائه شده قابل استفاده نیست.