Radix Sort – radix sort. The algorithm is similar to counting sort in that there is no comparison of elements, instead elements are *character-by-character* grouped into *buckets* (buckets), the bucket is selected by the index of the current number-character. Time complexity – O(nd).

Works like this:

• The input will be the numbers 6, 12, 44, 9
• Let’s create 10 buckets of lists (0-9) into which we will add/sort numbers bit by bit.

Further:

1. Run a loop with counter i up to the maximum number of characters in the number
2. At index i from right to left we get one character for each number, if there is no character, then we consider it to be zero
3. The character is converted to a number
4. Select a bucket by index – number, put the whole number there
5. After finishing iterating over numbers, convert all buckets back to a list of numbers
6. Get numbers sorted by digit
7. Repeat until all digits run out

``````import scala.collection.mutable.ListBuffer
import scala.util.Random.nextInt

def main(args: Array[String]) = {
var maxNumber = 200
var numbersCount = 30
var maxLength = maxNumber.toString.length() - 1

var referenceNumbers = LazyList.continually(nextInt(maxNumber + 1)).take(numbersCount).toList
var numbers = referenceNumbers

var buckets = List.fill(10)(ListBuffer[Int]())

for( i <- 0 to maxLength) { numbers.foreach( number => {
var numberString = number.toString
if (numberString.length() > i) {
var index = numberString.length() - i - 1
var character = numberString.charAt(index).toString
var characterInteger = character.toInt
buckets.apply(characterInteger) += number
}
else {
buckets.apply(0) += number
}
}
)
numbers = buckets.flatten
buckets.foreach(x => x.clear())
}
println(referenceNumbers)
println(numbers)
println(s"Validation result: \${numbers == referenceNumbers.sorted}")
}
}
``````

The algorithm also has a version for parallel execution, for example on the GPU; there is also a variant of bit sort, which is probably very interesting and truly breathtaking!