# 29 Merge 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: Speeding up appends

Consider the following code:

``````let size = 1024
var values: [Int] = []
// 1
for i in 0 ..< size {
values.append(i)
}
``````

This code will result in almost a dozen reallocations. Add a statement at `// 1` that reduces it to a single allocation.

Hint: `reserveCapacity` is your friend. ;]

### Challenge 2: Merge two sequences

Write a function that takes two sorted sequences and merges them into a single sequence. Here’s the function signature to start off:

``````func merge<T: Sequence>(first: T, second: T)
-> AnySequence<T.Element> where T.Element: Comparable {}
``````

## Solutions

### Solution to Challenge 1

``````let size = 1024
var values: [Int] = []
values.reserveCapacity(size)
for i in 0 ..< size {
values.append(i)
}
``````

Using `reserveCapacity` is a great way to speed up your appends.

### Solution to Challenge 2

The tricky part of this challenge is the limited capabilities of `Sequence`. Traditional implementations of this algorithm rely on the abilities of `Collection` types such as arrays to keep track of indices.

``````func merge<T: Sequence>(first: T, second: T)
-> AnySequence<T.Element> where T.Element: Comparable {

// 1
var result: [T.Element] = []

// 2
var firstIterator = first.makeIterator()
var secondIterator = second.makeIterator()

// 3
var firstNextValue = firstIterator.next()
var secondNextValue = secondIterator.next()

// ...
}
``````
``````while let first = firstNextValue,
let second = secondNextValue {

if first < second { // 1
result.append(first)
firstNextValue = firstIterator.next()
} else if second < first { // 2
result.append(second)
secondNextValue = secondIterator.next()
} else { // 3
result.append(first)
result.append(second)
firstNextValue = firstIterator.next()
secondNextValue = secondIterator.next()
}
}
``````
``````while let first = firstNextValue {
result.append(first)
firstNextValue = firstIterator.next()
}

while let second = secondNextValue {
result.append(second)
secondNextValue = secondIterator.next()
}

return AnySequence<T.Element>(result)
``````
``````var array1 = [1, 2, 3, 4, 5, 6, 7, 8]
var array2 = [1, 3, 4, 5, 5, 6, 7, 7]

for element in merge(first: array1, second: array2) {
print(element)
}
``````
``````1
1
2
3
3
4
4
5
5
5
6
6
7
7
7
8
``````

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: