Counting Sort
This page assumes you know prefix sums.
Note
This page is not about radix sort.
This page gives a brief introduction to counting sort.
Definition
Counting sort is a linear-time sorting algorithm.
Procedure
Counting sort uses an extra array \(C\) whose \(i\)-th element is the number of elements equal to \(i\) in \(A\), the array to be sorted. It then uses \(C\) to put the elements of \(A\) into their correct positions.1
It works in three steps:
- Count how many times each number occurs;
- Compute the prefix sums of these counts;
- Using the prefix sums of the counts, compute the rank of each number, going from right to left.
Why compute prefix sums
Rebuilding the array from the counts is enough to sort bare keys, duplicates included. To rearrange the original records stably, use the prefix sums of the counts to determine the output positions.
Computing the prefix sum at every entry of the extra array \(C\) and combining it with the value of the entry itself gives each of the duplicate elements a unique rank:
The value of an entry of \(C\) is the number of duplicate elements with that key, and the prefix sum at that entry is the rank of the last of these duplicates.
If we place the elements in the reverse of their order in \(A\), the sorted array clearly keeps the original order of \(A\) (among elements with the same key), so we get a stable sorting algorithm.
Properties
Stability
Counting sort is a stable sorting algorithm.
Time complexity
Counting sort runs in \(O(n+w)\), where \(w\) is the size of the value range of the data to be sorted.
Implementation
Pseudocode
1 2 3 4 5 6 7 8 9 10 11 12 13 | |
1 2 3 4 5 6 7 8 9 10 11 | |
References and notes
-
Counting sort - Wikipedia, the free encyclopedia (in Chinese) ↩
This page is an unofficial English translation of the original OI Wiki page (revision b469442a), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: ouuan, 24OI-bot, NachtgeistW, Konano, Enter-tainer, iamtwz, Xeonacid, mcendu, Alisahhh, ksyx, Junyan721113, minghu6, Great-designer, Menci, shawlleyw, gi-b716, Tiphereth-A, TrickEye, sun2snow, c-forrest (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.