# 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.  