Sorting data is one of the most common tasks in programming, especially when working with numbers like IDs, prices, or scores. While many sorting algorithms compare values directly, Radix Sort works in a very different and interesting way. Instead of comparing numbers as a whole, it sorts them digit by digit. This makes Radix Sort very fast for certain types of data, especially large lists of numbers with the same length.
with hands-on learning.
get the skills and confidence to land your next move.
Radix Sort is often used in systems where speed really matters, such as databases, searching systems, and low-level performance tools. Even though the idea sounds advanced at first, it becomes easy once you see how digits are processed step by step. In this article, we will explore how to write an F# program to implement Radix Sort using simple logic and clear examples that beginners can follow comfortably.
Program 1: Radix Sort Using Loops and Arrays
This program shows the classic Radix Sort approach using loops and arrays. It processes numbers digit by digit starting from the least significant digit.
open System
let getMax (arr:int[]) =
arr |> Array.max
let countingSort (arr:int[]) exp =
let output = Array.zeroCreate arr.Length
let count = Array.zeroCreate 10
for i in 0 .. arr.Length - 1 do
let index = (arr.[i] / exp) % 10
count.[index] <- count.[index] + 1
for i in 1 .. 9 do
count.[i] <- count.[i] + count.[i - 1]
for i in arr.Length - 1 .. -1 .. 0 do
let index = (arr.[i] / exp) % 10
output.[count.[index] - 1] <- arr.[i]
count.[index] <- count.[index] - 1
for i in 0 .. arr.Length - 1 do
arr.[i] <- output.[i]
let radixSort (arr:int[]) =
let maxVal = getMax arr
let mutable exp = 1
while maxVal / exp > 0 do
countingSort arr exp
exp <- exp * 10
[<EntryPoint>]
let main argv =
let numbers = [| 170; 45; 75; 90; 802; 24; 2; 66 |]
radixSort numbers
printfn "Sorted array:"
numbers |> Array.iter (printf "%d ")
0This program works by sorting the array based on one digit at a time using counting sort. It is useful because it avoids direct comparisons between numbers. Beginners can understand this by focusing on how digits are grouped and reordered at each step.
Program 2: Radix Sort with Clear Helper Functions
This version focuses on clarity by separating each task into small helper functions. It helps beginners understand each step without confusion.
open System
let digitAt num exp =
(num / exp) % 10
let radixSort (arr:int[]) =
let maxVal = Array.max arr
let mutable exp = 1
while maxVal / exp > 0 do
let buckets = Array.init 10 (fun _ -> ResizeArray<int>())
for value in arr do
let d = digitAt value exp
buckets.[d].Add value
let mutable index = 0
for bucket in buckets do
for value in bucket do
arr.[index] <- value
index <- index + 1
exp <- exp * 10
[<EntryPoint>]
let main argv =
let data = [| 88; 410; 1772; 20; 3; 59 |]
radixSort data
printfn "Sorted array:"
data |> Array.iter (printf "%d ")
0This program uses buckets to group numbers by digits. It is very beginner-friendly because it shows how values move from one place to another. Understanding this version makes the Radix Sort idea feel much more natural.
Program 3: Radix Sort Using Lists
This program demonstrates Radix Sort using lists instead of arrays. It fits well with functional programming ideas in F#.
open System
let radixSort (list : int list) =
let maxVal = List.max list
let rec sortByExp lst exp =
if maxVal / exp = 0 then lst
else
let buckets =
lst
|> List.groupBy (fun x -> (x / exp) % 10)
|> Map.ofList
let newList =
[0..9]
|> List.collect (fun d ->
match Map.tryFind d buckets with
| Some values -> values
| None -> []
)
sortByExp newList (exp * 10)
sortByExp list 1
[<EntryPoint>]
let main argv =
let numbers = [170; 45; 75; 90; 802; 24; 2; 66]
let sorted = radixSort numbers
printfn "Sorted list:"
sorted |> List.iter (printf "%d ")
0This version is helpful for beginners learning functional thinking. It avoids mutable state and focuses on transformation. It also shows how Radix Sort logic can work without arrays.
Program 4: Radix Sort Step by Step with Simple Logic
This program keeps the logic very slow and explicit so beginners can trace it easily.
open System
let radixSort (arr:int[]) =
let maxVal = Array.max arr
let mutable exp = 1
while maxVal / exp > 0 do
let temp = Array.zeroCreate arr.Length
let count = Array.zeroCreate 10
for value in arr do
count.[(value / exp) % 10] <- count.[(value / exp) % 10] + 1
for i in 1 .. 9 do
count.[i] <- count.[i] + count.[i - 1]
for i in arr.Length - 1 .. -1 .. 0 do
let d = (arr.[i] / exp) % 10
temp.[count.[d] - 1] <- arr.[i]
count.[d] <- count.[d] - 1
Array.blit temp 0 arr 0 arr.Length
exp <- exp * 10
[<EntryPoint>]
let main argv =
let values = [| 121; 432; 564; 23; 1; 45; 788 |]
radixSort values
printfn "Sorted array:"
values |> Array.iter (printf "%d ")
0This version clearly shows how each digit pass rearranges the numbers. It is perfect for beginners who want to understand every single step. Tracing this code builds strong confidence.
Program 5: Radix Sort for Non-Negative Integers Only
This program focuses only on non-negative numbers, which is the most common use case for Radix Sort.
open System
let radixSort (arr : int[]) =
let mutable exp = 1
let maxVal = Array.max arr
while maxVal / exp > 0 do
let buckets = Array.init 10 (fun _ -> [])
for num in arr do
let digit = (num / exp) % 10
buckets.[digit] <- buckets.[digit] @ [num]
let merged =
buckets
|> Array.collect List.toArray
Array.blit merged 0 arr 0 arr.Length
exp <- exp * 10
[<EntryPoint>]
let main argv =
let numbers = [| 90; 11; 234; 45; 9; 100 |]
radixSort numbers
printfn "Sorted array:"
numbers |> Array.iter (printf "%d ")
0This program is useful because it keeps the idea very focused and simple. Beginners can easily apply this version when working with IDs or numeric codes. It also reinforces how digits drive the sorting process.
Program 6: Radix Sort for Negative Numbers Only
This program focuses only on sorting negative integers using Radix Sort. Since Radix Sort works naturally with non-negative numbers, this approach first converts negative values into positive ones, sorts them, and then restores the negative sign at the end. This keeps the logic simple and beginner-friendly.
open System
let radixSortNegativeOnly (arr:int[]) =
// Convert all negative numbers to positive
let positives = arr |> Array.map (fun x -> -x)
let maxVal = Array.max positives
let mutable exp = 1
while maxVal / exp > 0 do
let output = Array.zeroCreate positives.Length
let count = Array.zeroCreate 10
for i in 0 .. positives.Length - 1 do
let index = (positives.[i] / exp) % 10
count.[index] <- count.[index] + 1
for i in 1 .. 9 do
count.[i] <- count.[i] + count.[i - 1]
for i in positives.Length - 1 .. -1 .. 0 do
let index = (positives.[i] / exp) % 10
output.[count.[index] - 1] <- positives.[i]
count.[index] <- count.[index] - 1
Array.blit output 0 positives 0 positives.Length
exp <- exp * 10
// Restore negative values and reverse order
positives
|> Array.rev
|> Array.map (fun x -> -x)
|> Array.iteri (fun i v -> arr.[i] <- v)
[<EntryPoint>]
let main argv =
let numbers = [| -170; -45; -75; -90; -802; -24; -2; -66 |]
radixSortNegativeOnly numbers
printfn "Sorted negative array:"
numbers |> Array.iter (printf "%d ")
0This program works by first turning all negative numbers into positive values so that Radix Sort can be applied normally. After sorting, the array is reversed because larger absolute values actually represent smaller negative numbers. Finally, the negative sign is restored. This approach is very useful for beginners because it avoids complex logic while still showing how Radix Sort can be adapted for special cases like negative-only data.
Frequently Asked Questions (FAQ)
This section answers common beginner questions about Radix Sort in a simple and friendly way.
Q1. What makes Radix Sort different from other sorting algorithms?
Radix Sort does not compare numbers directly. It sorts them digit by digit, which can be much faster for large datasets.
Q2. Is Radix Sort faster than Quick Sort?
For numbers with fixed length, Radix Sort can be faster. However, Quick Sort is more flexible for general data.
Q3. Can Radix Sort handle negative numbers?
Basic Radix Sort works best with non-negative numbers. Extra logic is needed for negative values.
Q4. Is Radix Sort hard for beginners?
It may feel unusual at first, but once the digit idea is clear, it becomes easy to understand.
Q5. Where is Radix Sort used in real life?
Radix Sort is used in databases, sorting IDs, and systems that need very fast numeric sorting.
Conclusion
Radix Sort is a powerful and unique sorting algorithm that works very differently from comparison-based methods. In this article, we explored several F# programs that implement Radix Sort using arrays, lists, loops, and clear helper logic. Each example showed how digits guide the sorting process step by step.
The best way to master Radix Sort is to practice with different numbers and trace each digit pass. With time and patience, Radix Sort will become a valuable tool in your F# programming journey and will strengthen your overall understanding of efficient sorting techniques.
