Visualizing the Radix Sort in Flutter

1. What Is Radix Sort?

Radix Sort is a non-comparative sorting algorithm that sorts numbers digit by digit, starting from the least significant digit (LSD) to the most significant digit (MSD). It’s especially efficient when working with integers or strings of uniform length.

Radix Sort uses Counting Sort as a subroutine to sort digits efficiently. It achieves linear time complexity for many practical cases, especially when the range of digits (k) is small compared to the number of items (n).

2. How Radix Sort Works

Let’s break it down:

Find the maximum number to determine the number of digits.
For each digit (starting from the rightmost/LSD):
- Use Counting Sort to sort the array based on that digit.
Repeat until all digits are processed.

This ensures the number is fully sorted.

3. Radix Sort Pseudocode

textCopyEditfunction radixSort(array):
    maxVal = findMax(array)
    exp = 1
    while maxVal / exp > 0:
        countingSortByDigit(array, exp)
        exp *= 10

Here, exp is 1 for the units place, 10 for tens, etc.

4. Step-by-Step Example

Sort: [170, 45, 75, 90, 802, 24, 2, 66]

Step 1: Sort by Units Digit (exp = 1)

csharpCopyEdit[170, 90, 802, 2, 24, 45, 75, 66]

Step 2: Sort by Tens Digit (exp = 10)

csharpCopyEdit[802, 2, 24, 45, 66, 170, 75, 90]

Step 3: Sort by Hundreds Digit (exp = 100)

csharpCopyEdit[2, 24, 45, 66, 75, 90, 170, 802]

Final Sorted:

5. Time and Space Complexity

Case	Time Complexity
Best	O(n·k)
Average	O(n·k)
Worst	O(n·k)

Where:

n = number of elements
k = number of digits in the largest number
Space Complexity: O(n + k)
Stable Sort: Yes

6. Radix Sort in Dart (Flutter-Friendly)

dartCopyEditFuture<void> radixSort(List<int> array, Function(List<int>) onUpdate) async {
  int getMax(List<int> arr) => arr.reduce((a, b) => a > b ? a : b);

  Future<void> countingSortByDigit(int exp) async {
    int n = array.length;
    List<int> output = List.filled(n, 0);
    List<int> count = List.filled(10, 0);

    // Count occurrences of digits
    for (int i = 0; i < n; i++) {
      int digit = (array[i] ~/ exp) % 10;
      count[digit]++;
    }

    // Cumulative count
    for (int i = 1; i < 10; i++) {
      count[i] += count[i - 1];
    }

    // Build output array (in reverse for stability)
    for (int i = n - 1; i >= 0; i--) {
      int digit = (array[i] ~/ exp) % 10;
      output[count[digit] - 1] = array[i];
      count[digit]--;
    }

    array.setAll(0, output);
    onUpdate(List.from(array));
    await Future.delayed(Duration(milliseconds: 500));
  }

  int maxVal = getMax(array);
  for (int exp = 1; maxVal ~/ exp > 0; exp *= 10) {
    await countingSortByDigit(exp);
  }
}

7. Visualization with Flutter + CustomPaint

In Flutter, visualize Radix Sort by:

Drawing vertical bars for each number.
Highlighting the current digit column being processed (e.g., units, tens, hundreds).
Triggering a repaint for each onUpdate() step to animate the digit-based sorting progression.
Optionally, display the value of the digit currently being used in sorting over each bar.

This makes it extremely visual and ideal for educational purposes.

8. When Should You Use Radix Sort?

Radix Sort is great when:

You’re sorting positive integers with a small number of digits.
You want a stable and fast non-comparison sort.
You’re processing large datasets with uniform-width keys.

Avoid if:

You need to sort floating-point numbers or negatives (requires extra handling).
Memory usage is a concern due to temporary arrays.

9. Summary

Radix Sort offers a powerful way to sort numbers by processing them digit-by-digit using Counting Sort as a stable subroutine. It’s one of the few sorting algorithms that can outperform comparison sorts in specific use cases.

Its stepwise nature makes it perfect for visualization, especially in educational apps.

Up next in our series: a unique twist — Cocktail Sort 🍸 — an elegant variation of Bubble Sort that sorts in both directions!