در مطلب حد پایین برای مسئله‌ی مرتب‌سازی ثابت کردیم که به‌ازای تمامی الگوریتم‌های مرتب‌سازی که بر پایه‌ی مقایسه‌ی عناصر ورودی کار می‌کنند، سریع‌ترین آن‌ها حداقل از مرتبه‌ی O(n log n) است و کمتر از آن امکان‌پذیر نیست. این حد پایین فقط برای الگوریتم‌هایی است که هیچ پیش شرطی برای ورودی و ساختار عناصر ندارند و صرفا با بکارگیری تکنیک‌هایی سعی دارند تعداد مشخصی عدد اعشاری را مرتب کنند.

الگوریتم مرتب‌سازی سریع (Quick Sort) نمونه‌ای از الگوریتم‌های مقایسه‌ای و از مرتبه‌ی O(n log n) است. که برای nهای بزرگ و حتی در بدترین حالت، همچنان از مرتبه‌ی زمانی O(n log n) بوده و لذا بهترین الگوریتم مرتب‌سازی است.

اگر عناصر ورودی را فقط از اعداد صحیح انتخاب کنیم و تعداد آنها نیز محدود و کم باشد، حالت خاصی را خواهیم داشت که می‌توان با مرتبه‌ی زمانی کمتر از O(n log n) یعنی با مرتبه‌ی زمانی O(n) آن را حل کرد. در این مطلب روش مرتب سازی شمارشی (Counting Sort) را برای این‌گونه لیست‌های عددی ارائه می‌کنیم. دقت داشته باشید که فرض ما بر این است که اعداد ورودی همگی صحیح و مثبت هستند که بصورت گسسته داده شده‌اند، لکن اگر اعداد منفی هم داشته باشیم، به‌راحتی با یک تغییر مکان ( Shift)، مسئله را به وضعیت مفروض تبدیل می‌کنیم.

در الگوریتم مرتب‌سازی شمارشی برای آرایه‌ای از اعداد صحیح و مثبت A که شامل n عدد صحیح مثبت a₀، a₁، a₂،... و a_n-1 است، کار را با تعریف آرایه‌ی جدیدی به‌نام C متشکل از L عنصر صحیح و مثبت شروع می‌کنیم که مقدار L برابر طول بازه‌ی عناصر موجود در A، است و به‌صورت زیر تعریف می‌شود:

L = Max(A) - Min(A) + 1

تعاریف فوق به زبان C++ این‌چنین است:

const int MAX = 1000;
int A[MAX], C[MAX] = { 0 }, L;
void main() {
  L = max(A) - min(A) + 1;
}

در آرایه‌ی C تعداد تکرار هر یک از عناصر ورودی را محاسبه و ثبت می‌کنیم. هر عدد در آرایه‌ی A مانند a_i، داخل آرایه‌ی C در اندیس a_i شمارش می‌شود. یعنی از مقدار هر عدد بعنوان اندیس استفاده می‌شود (و به همین دلیل نمی‌توان با این روش اعداد اعشاری را مرتب کرد).

در ادامه‌ی کار توابع F_c و F_b را به شکل زیر تعریف می‌کنیم:

F_c(x) = x - Min(A)
F_b(x) = C_Fc(x) - 1

و در برنامه به زبان C++ این‌گونه تعریف می‌شوند:

int Fc(int x) {
  return x - Min;
}
int Fb(int x) {
  return C[Fc(x)] - 1;
}

مرتبه‌ی زمانی هر یک از این توابع O(1) است و در تعیین مرتبه‌ی زمانی الگوریتم تاثیری ندارند.
حال پس از تعاریف مورد نیاز، شروع به مرتب‌سازی می‌کنیم. ابتدا هر یک از عناصر آرایه‌ی C را به این‌شکل مقداردهی می‌کنیم:

∀ a ∈ A, C_Fc(a) = Count(a)

که در آن Count(a) تعداد عنصر a در آرایه‌ی ورودی A است. البته در هنگام پیاده‌سازی باید دقت کنیم که فراخوانی آن به‌ازای هر یک از عناصر آرایه‌ی A، مرتبه‌ی زمانی الگوریتم را به O(n²) نرساند وهمچنان از مرتبه‌ی O(n) باشد. روش انجام آن‌را در ادامه خواهیم دید.
بیایید با یک مثال کار را پیش ببریم. فرض می‌کنیم آرایه‌ی A شامل 10 عنصر به‌صورت زیر داده شده‌است:

20, 8, 7, 16, 12, 19, 20, 8, 15, 8

وضعیت سلول‌های آرایه‌ی A به این‌شکل خواهد بود:

اعداد ورودی از بازه‌ی بسته‌ی [7, 20] انتخاب شده‌اند، لذا Min(A) = 7، Max(A) = 20 و مقدار L (طول آرایه‌ی C) برابر است با:

L = Max(A) - Min(A) + 1 = 20 - 7 + 1 = 14

توجه داشته باشید که برای شمارش 10 عدد ورودی، آرایه‌ای به‌طول 14 در نظر گرفته‌ایم و این طول کاملا به مقدار اعداد ورودی و بازه‌ی آن‌ها بستگی دارد، لذا الگوریتم مرتب‌سازی شمارشی فقط در حالت‌های خاصی قابل استفاده است. به‌هرحال مقدار هر یک از خانه‌های آرایه‌ی C را در ابتدا برابر صفر قرار می‌دهیم:

برای هر یک از عناصر آرایه‌ی A، خانه‌ی متناظر آن را در C مقداردهی می‌کنیم. ابتدا مقدار تابع F_c را به‌ازای هر عنصر ورودی محاسبه کرده و از آن به‌عنوان اندیس دسترسی به خانه‌ی متناظر در آرایه‌ی C استفاده می‌کنیم و برای انجام عمل شمارش، مقدار آن خانه را در C یک واحد افزایش می‌دهیم. مثلاً برای A₀ که مقدار آن برابر 20 است داریم:

F_c(20) = 20 - Min(A) = 20 - 7 = 13

پس مقدار خانه‌ی شماره 13 در آرایه‌ی C را یک واحد افزایش می‌دهیم. بعد همین کار را برای A₁، سپس A₂ و... در آخر برای A₉ تکرار می‌کنیم. وضعیت خانه‌های آرایه‌ی C در پایان این عملیات باید به‌این‌صورت باشد:

مقادیر فوق اطلاعات جالبی در باره‌ی لیست اعداد ارائه می‌کند. مثلا مقدار 3 در دومین خانه بیانگر این است که دومین عدد (از لحاظ بزرگی) 3 بار تکرار شده است و این عبارت درستی است، چرا که دومین عدد در ترتیب درست، عدد 8 است و 3 بار در لیست ورودی تکرار شده است. اعداد صفر در جدول بالا مربوط به اعدادی از بازه‌ی بسته‌ی [7, 20] است که در لیست ورودی وجود ندارند مانند 9، 10، 11، 13 و ... و این اتلاف بیهوده‌ی حافظه، یکی از دلایل طرد این الگوریتم به‌شمار می‌رود.
بخشی از برنامه‌ی نوشته شده به زبان C++ که عملیات بالا را پیاده‌سازی می‌کند عبارت است از:

for (i = 0; i < n; i++)
  C[Fc(A[i])]++;

مرتبه‌ی زمانی این عملیات برابر O(n) است.

برای آشنایی با نماد O (اُ بزرگ) و دریافت جزئیات بیشتر در مورد مرتبه‌ی زمانی، مطلب مربوط به تحلیل کارایی و محاسبه‌ی پیچیدگی زمانی الگوریتم‌ها را ببینید.

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

اولین خانه همواره مقدار 1 دارد (چرا؟) و آخرین خانه باید برابر n باشد چون مجموع تکرار اعداد برابر با تعداد کل اعداد است. حال آرایه‌ی صحیح و مثبت B را با اندازه‌ی n تعریف کرده و اعداد را بصورت مرتب شده در آن می‌چینیم. به‌این‌صورت که به‌ازای هر عدد از آرایه‌ی A، مقدار تابع F_b را محاسبه کرده و آن را به‌عنوان اندیس دسترسی به آرایه‌ی B به‌کار می‌گیریم و عدد را در آن خانه قرار می‌دهیم. برای مثال، به‌ازای A₀ مقدار تابع F_b برابر است با:

F_b(20) = C_Fc(20) - 1 = C₁₃ - 1 = 10 - 1 = 9

یعنی عدد موجود در خانه‌ی A₀ در خانه‌ی شماره‌ی 9 در آرایه‌ی B قرار می‌گیرد. مقدار خانه‌ی 13 در آرایه‌ی C را نیز یک واحد کاهش می‌دهیم (چرا؟)
با توجه به‌این‌که اندیس‌های آرایه‌ی C آخرین محل هر عنصر در آرایه‌ی مرتب B را نشان می‌دهد، و ازطرفی ممکن است اعداد تکراری باشند، لذا اعداد آرایه‌ی C را بعد از استفاده یک واحد کاهش می‌دهیم تا محل جدید عدد (درصورت تکراری بودن)، خانه‌ی مجاور (قبلی) باشد. به هرحال اگر این روند را برای سایر اعداد ورودی تکرار کنیم، آرایه‌ی B به این‌شکل خواهد بود:

قبل از خاتمه‌ی کار، آرایه‌ی B را در A کپی می‌کنیم. قطعه برنامه‌ی زیر عملیات گفته شده را پیاده سازی می‌کند.

for(i = 0; i < n; i++) {
  B[Fb(A[i])] = A[i];
  C[Fc(A[i])]--;
}
for (i = 0; i < n; i++)
  A[i] = B[i];

براحتی می‌توان نشان داد که مرتبه‌ی زمانی هریک از حلقه‌های تکرار بالا O(n) است. برنامه‌ی کامل این الگوریتم به زبان C++ در زیر آورده شده‌است.

1#include <iostream>
2using namespace std;
3#define MAX 100
4int A[MAX], B[MAX], C[MAX] = { 0 }, Min;
5int Fc(int x) {
6  return x - Min;
7}
8int Fb(int x) {
9  return C[Fc(x)] - 1;
10}
11void main() {
12  int n, I, L = 0;
13  cin >> n;
14  for (I = 0; I < n; I++) {
15    cin >> A[I];
16    if (I == 0 || A[I] < Min)
17      Min = A[I];
18    if (A[I] - Min + 1 > L)
19      L = A[I] - Min + 1;
20  }
21  for (I = 0; I < n; I++)
22    C[Fc(A[I])]++;
23  for (I = 1; I < L; I++)
24    C[I] += C[I - 1];
25  for (I = 0; I < n; I++) {
26    B[Fb(A[I])] = A[I];
27    C[Fc(A[I])]--;
28  }
29  for (I = 0; I < n; I++)
30    A[I] = B[I];
31  for (I = 0; I < n; I++)
32    cout << A[I] << " ";
33}

توابع Fc() و Fb() را می‌توان حذف کرده و بجای آن‌ها دستور مستقیم محاسبه را در برنامه‌ی اصلی قرار داد. یا این‌که از محاسبه‌ی مقدار L صرف‌نظر کرد. حتی می‌توان کپی نهایی آرایه را نیز انجام نداد. به هرحال بهینه‌سازی کد و روش برنامه‌نویسی تا زمانی که مرتبه‌ی زمانی همان O(n) است، تاثیر چندانی در کارایی این الگوریتم ندارد.

1#include <iostream>
2using namespace std;
3#define MAX 100
4void main() {
5  int A[MAX], B[MAX], C[MAX] = { 0 }, MIN, n, I;
6  cin >> n;
7  for (I = 0; I < n; I++) {
8    cin >> A[I];
9    if (I == 0 || A[I] < MIN)
10      MIN = A[I];
11  }
12for (I = 0; I < n; I++)
13  C[A[I] - MIN]++;
14for (I = 1; I < MAX; I++)
15  C[I] += C[I - 1];
16for (I = 0; I < n; I++) {
17  B[C[A[I] - MIN] - 1] = A[I];
18  C[A[I] - MIN]--;
19}
20for (I = 0; I < n; I++)
21  cout << B[I] << " ";
22}

نسخه‌ی دیگری از برنامه را در ادامه مشاهده می‌کنید که در آن، ترتیب اعداد از بزرگ به کوچک است. با توجه به این‌که در این روش مرتب‌سازی، مقایسه‌ای بین اعداد انجام نمی‌گیرد، لذا نمی‌توان مانند روش‌های مرتب‌سازی مقایسه‌ای، با معکوس کردن عملگر مقایسه به ترتیب برعکس دست یافت.

1#include <iostream>
2using namespace std;
3#define MAX 100
4void main() {
5  int A[MAX], B[MAX], C[MAX] = { 0 }, MIN, n, I;
6  cin >> n;
7  for (I = 0; I < n; I++) {
8    cin >> A[I];
9    if (I == 0 || A[I] < MIN)
10      MIN = A[I];
11  }
12for (I = 0; I < n; I++)
13  C[A[I] - MIN]++;
14for (I = 1; I < MAX; I++)
15  C[I] += C[I - 1];
16for (I = 0; I < n; I++) {
17  B[n - C[A[I] - MIN]] = A[I];
18  C[A[I] - MIN]--;
19}
20for (I = 0; I < n; I++)
21  cout << B[I] << " ";
22}

در الگوریتم مرتب‌سازی شمارشی، هیچ مقایسه‌ای بین عناصر آرایه‌ی ورودی انجام نمی‌گیرد و صرفا از خاصیت اعداد صحیح برای جانمایی استفاده می‌شود. از این‌رو نمی‌توان آن را جز الگوریتم‌های عمومی مرتب‌سازی به‌حساب آورد.

البته می‌توان تابع Fb() را در دونسخه‌ی مختلف برای مرتب‌سازی صعودی (Ascending) و نزولی (Descending) نوشت:

int Fb_ASC(int x) {
  return C[Fc(x)] - 1;
}
int Fb_DESC(int x) {
  return n - C[Fc(x)];
}