## Data Structures & Algorithms in Swift

Fourth Edition · iOS 15 · Swift 5.5 · Xcode 13

#### Before You Begin

Section 0: 6 chapters

#### Section I: Introduction

Section 1: 3 chapters

#### Section II: Elementary Data Structures

Section 2: 6 chapters

# 29. Merge Sort Challenges Written by Kelvin Lau

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

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