# 31 Radix Sort Challenges Written by Kelvin Lau

You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

### Challenge 1: Most significant digit

Open the starter playground for this chapter to begin.

The implementation discussed in the chapter used a least significant digit radix sort. Your task is to implement a most significant digit radix sort.

This sorting behavior is called lexicographical sorting and is also used for `String` sorting.

For example:

``````var array = [500, 1345, 13, 459, 44, 999]
array.lexicographicalSort()
print(array) // outputs [13, 1345, 44, 459, 500, 999]
``````

## Solution to Challenge 1

MSD radix sort is closely related to LSD radix sort, in that both utilize bucket sort. The difference is that MSD radix sort needs to carefully curate subsequent passes of the bucket sort. In LSD radix sort, bucket sort ran repeatedly using the whole array for every pass. In MSD radix sort, you run bucket sort with the whole array only once. Subsequent passes will sort each bucket recursively.

#### Digits

``````extension Int {

var digits: Int {
var count = 0
var num = self
while num != 0 {
count += 1
num /= 10
}
return count
}

func digit(atPosition position: Int) -> Int? {
guard position < digits else {
return nil
}
var num = self
let correctedPosition = Double(position + 1)
while num / Int(pow(10.0, correctedPosition)) != 0 {
num /= 10
}
return num % 10
}
}
``````

#### Lexicographical sort

With the helper methods, you’re now equipped to deal with MSD radix sort. Write the following at the bottom of the playground:

``````extension Array where Element == Int {

mutating func lexicographicalSort() {
}

private func msdRadixSorted(_ array: [Int], _ position: Int) -> [Int] {
// more to come...
}
}
``````
``````private func msdRadixSorted(_ array: [Int], _ position: Int) -> [Int] {

// 1
var buckets: [[Int]] = .init(repeating: [], count: 10)
// 2
var priorityBucket: [Int] = []

// 3
array.forEach { number in
guard let digit = number.digit(atPosition: position) else {
priorityBucket.append(number)
return
}
buckets[digit].append(number)
}

// more to come...
}
``````
``````priorityBucket.append(contentsOf: buckets.reduce(into: []) {
result, bucket in
guard !bucket.isEmpty else {
return
}
})

return priorityBucket
``````

#### Base case

As with all recursive operations, you need to set a terminating condition that stops the recursion. Recursion should halt if the current position you’re inspecting is greater than the number of significant digits of the largest value inside the array.

``````private var maxDigits: Int {
self.max()?.digits ?? 0
}
``````
``````guard position < array.maxDigits else {
return array
}
``````
``````var array: [Int] = (0...10).map { _ in Int(arc4random()) }
array.lexicographicalSort()
print(array)
``````
``````[1350975449, 1412970969, 1727253826, 2003696829, 2281464743, 2603566662, 3012182591, 3552993620, 3665442670, 4167824072, 465277276]
``````

Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.

Have feedback to share about the online reading experience? If you have feedback about the UI, UX, highlighting, or other features of our online readers, you can send them to the design team with the form below:  