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:

- Run a loop with counter i up to the maximum number of characters in the number
- 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
- The character is converted to a number
- Select a bucket by index – number, put the whole number there
- After finishing iterating over numbers, convert all buckets back to a list of numbers
- Get numbers sorted by digit
- Repeat until all digits run out

Radix Sort example in Scala:

```
import scala.collection.mutable.ListBuffer
import scala.util.Random.nextInt
object RadixSort {
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!**

### Links

https://gitlab.com/demensdeum/algorithms/-/blob/master/sortAlgorithms/radixSort/radixSort.scala

### Sources

https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%80%D0%B0%D0%B7%D1%80% D1%8F%D0%B4%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0% B2%D0%BA%D0%B0

https://www.geeksforgeeks.org/radix-sort/

https://www.youtube.com/watch?v=toAlAJKojos

https://github.com/gyatskov/radix-sort