C++UCS301
Sorting AlgorithmsC++17

Radix Sort

Radix sort processes keys one digit at a time using a stable sub-sort such as counting sort.

What to understand

  • LSD and MSD variants
  • Stable digit sorting
  • Base selection
  • Fixed-width keys

Remember this

  1. 1Digit sort must be stable
  2. 2Time O(d(n+b))
  3. 3Not a comparison sort
  4. 4Common for integers and strings

Detailed notes

Radix sort orders composite keys one position at a time. Least-significant-digit sorting starts at the lowest digit and depends on a stable sub-sort so earlier digit order survives later passes.

With d digits, n items, and base b, work is O(d(n+b)). A larger base reduces digit passes but enlarges count arrays and may worsen cache behaviour.

How it works

  1. 1Choose a representation and base.
  2. 2Extract the current digit from every key.
  3. 3Stable-sort by that digit.
  4. 4Advance until every significant position has been processed.

Worked trace

LSD passes

[170,45,75,90,802,24,2,66]
  1. 1Stable-sort by units → [170,90,802,2,24,45,75,66].
  2. 2Stable-sort by tens → [802,2,24,45,66,170,75,90].
  3. 3Stable-sort by hundreds.
  4. 4No more significant digits remain.
Result: [2,24,45,66,75,90,170,802]

Where it is used

  • Fixed-width integers
  • Dates and structured identifiers
  • Strings with controlled alphabets

Common mistakes

  • Using an unstable digit sort
  • Ignoring signed-number representation
  • Overflowing the decimal place multiplier

Complexity analysis

OperationBestAverageWorstExtra space
SortO(d(n+b))O(d(n+b))O(d(n+b))O(n+b)

C++ implementation

C++17 reference
main.cpp

LSD radix sort for non-negative integers

Stable counting sort by each decimal digit preserves the ordering established by earlier digits.

void radixSort(vector<int>& values) {
    int maximum = *max_element(values.begin(), values.end());
    for (int place = 1; maximum / place > 0; place *= 10) {
        vector<int> count(10), output(values.size());
        for (int value : values) ++count[(value / place) % 10];
        for (int d = 1; d < 10; ++d) count[d] += count[d - 1];
        for (int i = static_cast<int>(values.size()) - 1; i >= 0; --i) {
            int digit = (values[i] / place) % 10;
            output[--count[digit]] = values[i];
        }
        values = move(output);
    }
}
13 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.