mastorna.it
IT

Sorting algorithms · 6/7

Radix sort (LSD)

Sorts from the least significant digit using stable passes.

Average timeΘ(d(n + b)) SpaceΘ(n + b) StableYes In placeNo

How it works

Group by units, then tens, hundreds and so on; stability preserves earlier digit ordering.

Invariant: After position exp, the array is ordered by all digits up through exp.

Step-by-step visualization

Each bar represents one element. Colors identify compared elements, the pivot or key, the final region and the active range.

Use 2 to 16 values. This visualizer accepts values from 0 to 999.

Comparisons
0
Writes
0
Swaps
0
Pass / level
0
active comparison pivot / key final

Pseudocode linked to the visualization

  1. exp ← 1
  2. while max(A) / exp > 0
  3. stably sort by digit (value / exp) mod 10
  4. distribute values into queues 0 … 9
  5. concatenate queues in order
  6. exp ← exp · 10

The highlighted line corresponds to the operation described by the visualizer. Index-management details are intentionally simplified.

Complexity analysis

Best caseΘ(d(n + b))

All d digits are scanned, with n elements and b buckets per digit: Θ(d(n+b)).

Average caseΘ(d(n + b))

Initial order does not change the number of passes.

Worst caseΘ(d(n + b))

For at most d digits the same Θ(d(n+b)) bound applies.

Auxiliary spaceΘ(n + b)

A stable pass uses Θ(n+b) memory and stability is required for LSD correctness.

Properties at a glance

Stable

Stability concerns the relative order of elements with equal keys.

Not in place

This classification refers to the version shown on this page.

When to use it and what to avoid

A good choice when…

Good for nonnegative integers, identifiers and bounded-length strings.

Common mistake

An unstable digit sort erases previous work; signs need explicit handling.