Radix Sort is one of those sorting techniques that feels different from the rest because it does not compare values the way algorithms like Quick Sort or Heap Sort do. Instead, it works by examining numbers digit by digit, starting from the lowest place value and moving upward. This makes it a reliable and predictable algorithm, especially when dealing with large lists of numbers that share similar lengths. Many beginners enjoy learning Radix Sort because it helps them think about sorting from a fresh angle, one that focuses more on the structure of data rather than comparisons.
with hands-on learning.
get the skills and confidence to land your next move.
In real-world applications, Radix Sort becomes helpful when sorting long lists of integers, postal codes, phone numbers, or any data where each element can be broken into digit positions. Its steady running time and simple logic make it popular in systems that need stable and efficient sorting. Learning Radix Sort in Scala also shows how functional styles and clean code can make the algorithm even easier to understand. Once you explore its steps, you will notice how smoothly it processes data, which makes it a great addition to your toolbox as you grow your programming skills.
Program 1: Basic Radix Sort Using Counting Sort for Digits
This first program demonstrates the classic form of Radix Sort, which uses Counting Sort as a helper to arrange digits from the lowest to the highest place value. It is the most common way beginners learn the algorithm.
object RadixSortBasic {
def getMax(arr: Array[Int]): Int = arr.max
def countingSort(arr: Array[Int], exp: Int): Unit = {
val n = arr.length
val output = new Array[Int](n)
val count = new Array[Int](10)
for (i <- arr.indices) {
val digit = (arr(i) / exp) % 10
count(digit) += 1
}
for (i <- 1 until 10) {
count(i) += count(i - 1)
}
for (i <- n - 1 to 0 by -1) {
val digit = (arr(i) / exp) % 10
output(count(digit) - 1) = arr(i)
count(digit) -= 1
}
for (i <- arr.indices) {
arr(i) = output(i)
}
}
def radixSort(arr: Array[Int]): Unit = {
var exp = 1
val max = getMax(arr)
while (max / exp > 0) {
countingSort(arr, exp)
exp *= 10
}
}
def main(args: Array[String]): Unit = {
val data = Array(170, 45, 75, 90, 802, 24, 2, 66)
radixSort(data)
println("Sorted Array: " + data.mkString(", "))
}
}This version works by identifying the largest number, then sorting by each digit position using Counting Sort. The algorithm starts with the units place, then tens, then hundreds, and continues until the entire number has been processed. Beginners find this method helpful because each stage feels simple and predictable, letting them see how small steps shape the final sorted list.
Program 2: Radix Sort Using Recursion for Digit Processing
This program shows how Radix Sort can also be done recursively by handling one digit place per recursive call. It gives learners another way to view the algorithm’s flow.
object RadixSortRecursive {
def getMax(arr: Array[Int]): Int = arr.max
def countingSort(arr: Array[Int], exp: Int): Unit = {
val output = new Array[Int](arr.length)
val count = new Array[Int](10)
for (num <- arr) count((num / exp) % 10) += 1
for (i <- 1 until 10) count(i) += count(i - 1)
for (i <- arr.length - 1 to 0 by -1) {
val digit = (arr(i) / exp) % 10
output(count(digit) - 1) = arr(i)
count(digit) -= 1
}
for (i <- arr.indices) arr(i) = output(i)
}
def radixRecursive(arr: Array[Int], exp: Int, max: Int): Unit = {
if (max / exp <= 0) return
countingSort(arr, exp)
radixRecursive(arr, exp * 10, max)
}
def main(args: Array[String]): Unit = {
val data = Array(51, 3, 256, 89, 102, 7)
val max = getMax(data)
radixRecursive(data, 1, max)
println("Sorted Array: " + data.mkString(", "))
}
}The recursive style handles each digit position in a natural and repeating pattern. Each call sorts the array by one digit and then passes control to the next place value. This makes it easy for learners to see how recursion fits into a step-by-step sorting task without making the code complicated.
Program 3: Radix Sort Using Lists Instead of Arrays
Here we use Scala lists to show how Radix Sort adapts to different data structures. Lists offer a more functional style that many Scala beginners enjoy.
object RadixSortList {
def getMax(lst: List[Int]): Int = lst.max
def countingSort(lst: List[Int], exp: Int): List[Int] = {
// Initialize buckets for digits 0-9
val buckets = Array.fill(10)(List[Int]())
// Add numbers to corresponding buckets (append to preserve order)
for (num <- lst) {
val digit = (num / exp) % 10
buckets(digit) = buckets(digit) :+ num // append instead of prepend
}
// Flatten buckets back into a single list
buckets.flatten.toList
}
def radixSort(lst: List[Int]): List[Int] = {
val max = getMax(lst)
def loop(current: List[Int], exp: Int): List[Int] = {
if (max / exp <= 0) current
else loop(countingSort(current, exp), exp * 10)
}
loop(lst, 1)
}
def main(args: Array[String]): Unit = {
val data = List(305, 21, 98, 402, 5, 16)
val sorted = radixSort(data)
println("Sorted List: " + sorted.mkString(", "))
}
}This approach places each number into buckets based on digits, then gathers them back into a single list. The functional design keeps the code clean and avoids modifying data directly, which is a great lesson for beginners who want to practice functional thinking.
Program 4: Radix Sort with Negative Numbers Handling
This version shows how to sort numbers that include both positive and negative values. Since basic Radix Sort handles only non-negative integers, this example extends the method.
object RadixSortBasic {
def getMax(arr: Array[Int]): Int = arr.max
def countingSort(arr: Array[Int], exp: Int): Unit = {
val n = arr.length
val output = new Array[Int](n)
val count = new Array[Int](10)
for (i <- arr.indices) {
val digit = (arr(i) / exp) % 10
count(digit) += 1
}
for (i <- 1 until 10) {
count(i) += count(i - 1)
}
for (i <- n - 1 to 0 by -1) {
val digit = (arr(i) / exp) % 10
output(count(digit) - 1) = arr(i)
count(digit) -= 1
}
for (i <- arr.indices) {
arr(i) = output(i)
}
}
def radixSort(arr: Array[Int]): Unit = {
var exp = 1
val max = getMax(arr)
while (max / exp > 0) {
countingSort(arr, exp)
exp *= 10
}
}
}
object RadixSortWithNegatives {
def radixSort(arr: Array[Int]): Unit = {
val positives = arr.filter(_ >= 0)
val negatives = arr.filter(_ < 0).map(Math.abs)
RadixSortBasic.radixSort(positives)
RadixSortBasic.radixSort(negatives)
val sortedNeg = negatives.reverse.map(_ * -1)
val result = sortedNeg ++ positives
for (i <- arr.indices) arr(i) = result(i)
}
def main(args: Array[String]): Unit = {
val data = Array(-12, 45, 0, -3, 27, -50, 19)
radixSort(data)
println("Sorted Array: " + data.mkString(", "))
}
}Here the negative numbers are separated, converted to positive, sorted, then restored and placed before all positive numbers. This technique helps beginners understand that while Radix Sort prefers non-negative integers, it can still work with negatives using a little creativity and careful handling.
Program 5: Radix Sort for Strings (Character-by-Character Sorting)
This final example shows how Radix Sort can be adapted to sort strings by processing characters from the end of the word toward the front.
object RadixSortStrings {
def radixSort(arr: Array[String]): Unit = {
if (arr.isEmpty) return
val maxLength = arr.map(_.length).max
// Sort from least significant character to most significant
for (pos <- maxLength - 1 to 0 by -1) {
// Buckets for all ASCII characters (0-255)
val buckets = Array.fill(256)(List[String]())
// Place words in buckets, using 0 for missing characters
for (word <- arr) {
val c = if (pos < word.length) word(pos).toInt else 0
buckets(c) = buckets(c) :+ word // append to preserve order
}
// Merge buckets back into the array
val merged = buckets.flatten
for (i <- arr.indices) arr(i) = merged(i)
}
}
def main(args: Array[String]): Unit = {
val words = Array("cat", "apple", "banana", "axe", "car")
radixSort(words)
println("Sorted Words: " + words.mkString(", "))
}
}Sorting strings with Radix Sort demonstrates how flexible the algorithm can be. By treating each character as a digit, the program can order words in a stable and predictable way. Beginners find this exciting because it expands Radix Sort beyond numbers and shows how creative problem-solving brings algorithms to new areas.
Frequently Asked Questions (FAQ)
This section answers common questions that beginners often have when first learning Radix Sort in Scala. Each answer is kept short and clear to help you understand the main ideas without confusion.
Q1: Why does Radix Sort not compare numbers directly?
Radix Sort works by using digits as groups, so it avoids comparing values and instead organizes them based on place positions.
Q2: Is Radix Sort faster than Quick Sort?
Radix Sort can be faster when all numbers have similar lengths, but Quick Sort is often faster for general use cases.
Q3: Can Radix Sort work with negative numbers?
Yes, but only with extra handling, because the classic version works with non-negative integers.
Q4: Does Radix Sort sort strings too?
It can, as long as each character is processed like a digit, usually from right to left.
Q5: Is Radix Sort stable?
Yes, Radix Sort is naturally stable because it preserves the order of equal elements during digit processing.
Conclusion
Radix Sort is a refreshing algorithm to study when you want to move beyond comparison-based sorting and explore a more structured, digit-oriented approach. Its clear steps and predictable flow make it friendly for beginners and powerful in real applications that work with large sets of numbers or texts. By trying different versions in Scala—including arrays, lists, recursion, and special handling for strings—you gain a wide understanding of how flexible and reliable this technique can be.
As you continue practicing, experiment with your own data and try adapting Radix Sort to different scenarios. Each attempt helps you grow more comfortable with algorithmic thinking, and soon you will find yourself applying these ideas naturally in your programming projects.
