C# Counting Sort
last modified November 6, 2026
In this article we implement the counting sort algorithm in C#. We sort
integers and letters, write the stable version that sorts records by an integer
key, and show when counting sort beats Array.Sort.
Sorting is arranging the elements of a collection in a specific order, for instance from the smallest to the largest. A sorting algorithm is the sequence of steps that produces this order.
Counting sort algorithm
Counting sort does not compare elements. It works with integer keys from a known, small range. The algorithm counts how many times each key occurs and then writes the keys out in order, each as many times as it was counted.
| Property | Value |
|---|---|
| Time | O(n + k), where k is the size of the key range |
| Extra memory | O(k) for the counts, O(n + k) for the stable version |
| Stable | yes, in the version with prefix sums |
Comparison sorts cannot be faster than O(n log n). Counting sort is linear, but
only when the range k is not much larger than n.
Sorting ten numbers between 0 and a billion needs a count array with a billion
elements. Counting sort suits data such as ages, grades, bytes, or letters.
C# counting sort example
The first example sorts an array of integers, including negative ones.
int[] nums = [4, -2, 2, 8, 3, -2, 3, 1, 0];
CountingSort(nums);
Console.WriteLine(string.Join(" ", nums));
static void CountingSort(int[] arr)
{
if (arr.Length == 0) return;
int min = arr.Min();
int max = arr.Max();
int[] counts = new int[max - min + 1];
foreach (int x in arr)
{
counts[x - min]++;
}
int k = 0;
for (int v = 0; v < counts.Length; v++)
{
for (int c = 0; c < counts[v]; c++)
{
arr[k++] = v + min;
}
}
}
The method overwrites the array with the sorted values.
int min = arr.Min(); int max = arr.Max(); int[] counts = new int[max - min + 1];
The count array covers the range from the minimum to the maximum. Subtracting the minimum maps the values to array indexes starting at zero, so negative numbers work too.
foreach (int x in arr)
{
counts[x - min]++;
}
For each value, we increase its counter.
for (int v = 0; v < counts.Length; v++)
{
for (int c = 0; c < counts[v]; c++)
{
arr[k++] = v + min;
}
}
We walk the counts in ascending order and write each value as many times as it occurred.
$ dotnet run -2 -2 0 1 2 3 3 4 8
Sorting letters
The 26 lowercase English letters form a small range, ideal for counting sort. The next example sorts the letters of a word in both directions.
string word = "mississippi";
Console.WriteLine(SortLetters(word, descending: false));
Console.WriteLine(SortLetters(word, descending: true));
static string SortLetters(string text, bool descending)
{
int[] counts = new int[26];
foreach (char c in text)
{
counts[c - 'a']++;
}
return string.Create(text.Length, (counts, descending), static (span, state) =>
{
int k = 0;
for (int i = 0; i < 26; i++)
{
int letter = state.descending ? 25 - i : i;
int n = state.counts[letter];
span.Slice(k, n).Fill((char)('a' + letter));
k += n;
}
});
}
We count the letters and build the result string with
string.Create.
counts[c - 'a']++;
Subtracting 'a' maps the letters a to z to indexes 0 to 25. The
example assumes that the text contains only lowercase English letters.
return string.Create(text.Length, (counts, descending), static (span, state) =>
The string.Create method allocates a string of the given length and
lets us write its characters through a span. The state tuple passes the data
to a static lambda, which captures no variables.
int letter = state.descending ? 25 - i : i;
int n = state.counts[letter];
span.Slice(k, n).Fill((char)('a' + letter));
k += n;
For the descending order, we walk the counts backwards. The Fill
method writes a run of the same letter.
$ dotnet run iiiimppssss ssssppmiiii
Stable counting sort
The simple version writes out keys, so it cannot sort records. The stable version computes the final position of each element from prefix sums of the counts. It is the building block of radix sort.
Student[] students =
[
new("Adam", 3), new("Beth", 1), new("Carl", 2), new("Dana", 3),
new("Emil", 1), new("Fred", 2), new("Gina", 1),
];
Student[] sorted = CountingSort(students, s => s.Grade, maxKey: 5);
foreach (var s in sorted)
{
Console.WriteLine($"{s.Grade} {s.Name}");
}
static T[] CountingSort<T>(T[] items, Func<T, int> key, int maxKey)
{
int[] counts = new int[maxKey + 1];
foreach (var item in items)
{
counts[key(item)]++;
}
Console.WriteLine($"counts: {string.Join(" ", counts)}");
for (int i = 1; i < counts.Length; i++)
{
counts[i] += counts[i - 1];
}
Console.WriteLine($"positions: {string.Join(" ", counts)}");
T[] output = new T[items.Length];
for (int i = items.Length - 1; i >= 0; i--)
{
int k = key(items[i]);
output[--counts[k]] = items[i];
}
return output;
}
record Student(string Name, int Grade);
We sort students by their grade, from 1 to 5. The key is extracted with a
Func<T, int> delegate.
for (int i = 1; i < counts.Length; i++)
{
counts[i] += counts[i - 1];
}
After the prefix sums, counts[k] holds the number of elements with
a key less than or equal to k. This is the position just after the
last element with key k in the output.
for (int i = items.Length - 1; i >= 0; i--)
{
int k = key(items[i]);
output[--counts[k]] = items[i];
}
We place the elements from the end of the input. Each element goes to the last free position for its key, and the position is decremented. Walking backwards keeps the elements with equal keys in their original order, so the sort is stable.
Three students have grade 1, so they take positions 0 to 2 in the output; the two students with grade 2 take positions 3 and 4. Beth, Emil, and Gina keep their input order.
$ dotnet run counts: 0 3 2 2 0 0 positions: 0 3 5 7 7 7 1 Beth 1 Emil 1 Gina 2 Carl 2 Fred 3 Adam 3 Dana
Counting sort vs Array.Sort
In the last example, we sort ten million random ages between 0 and 119.
#:property PublishAot=false
using System.Diagnostics;
var rnd = new Random(17);
int[] ages = [.. Enumerable.Range(0, 10_000_000).Select(_ => rnd.Next(0, 120))];
int[] a = [.. ages];
var sw = Stopwatch.StartNew();
CountingSort(a);
Console.WriteLine($"Counting sort: {sw.ElapsedMilliseconds} ms");
int[] b = [.. ages];
sw.Restart();
Array.Sort(b);
Console.WriteLine($"Array.Sort: {sw.ElapsedMilliseconds} ms");
Console.WriteLine($"Same result: {a.SequenceEqual(b)}");
static void CountingSort(int[] arr)
{
int min = arr.Min();
int max = arr.Max();
int[] counts = new int[max - min + 1];
foreach (int x in arr) counts[x - min]++;
int k = 0;
for (int v = 0; v < counts.Length; v++)
{
arr.AsSpan(k, counts[v]).Fill(v + min);
k += counts[v];
}
}
The range is small compared with the number of elements, the best case for counting sort.
arr.AsSpan(k, counts[v]).Fill(v + min);
The Fill method of a span writes the runs of equal values faster
than an inner loop.
#:property PublishAot=false
File-based apps are published with Native AOT by default. The directive turns this off, so the release build does not pull in the AOT compiler package.
We run the program in the Release configuration. Counting sort is about ten
times faster than Array.Sort for this data.
$ dotnet run -c Release benchmark.cs Counting sort: 31 ms Array.Sort: 336 ms Same result: True
Source
In this article we have implemented the counting sort algorithm in C#.
Other sorting algorithms in C#:
- Bubble sort
- Selection sort
- Insertion sort
- Shell sort
- Merge sort
- Quick sort
- Heap sort
- Radix sort
- Bucket sort
Author
List all C# tutorials.