29. Merge Sort Challenges

Written by Kelvin Lau

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 {}

AnySequence is a type eraser that abstracts away the concrete implementation details.

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.

Since Sequence types have no notion of indices, you’ll make use of their iterator.

Open the starter project to begin. Update its contents to the following:

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()

  // ...
}

Setting up the algorithm involves the following steps:

1. Create a new container to store the merged sequences.

2. Grab the iterators of the first and second sequences. Iterators sequentially dispense values of the sequence via the next method.

3. Create two variables that are initialized as the first and second iterator’s first value. next returns an optional element of the sequence, and a nil return value suggests the iterator has dispensed all elements in the sequence.

Using the iterators, you’ll decide which element should be appended into the result array by comparing the first and second next values. Write the following at the end of the merge function:

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()
  }
}

This code is the main component of the merging algorithm. Using while let, you check to see if it’s necessary to compare which values are to be inserted into the result array.

1. If the first value is less than the second one, you’ll append the first value in result and seed the next value to be compared with by invoking next on the first iterator.
2. If the second value is less than the first, you’ll do the opposite. You seed the next value to be compared by invoking next on the second iterator.
3. You append both the first and second values and seed both next values if they are equal.

This process will continue until one of the iterators run out of elements to dispense. In that scenario, it means the iterator with elements left has elements equal to or greater than the current values in result.

To add the rest of those values, write the following at the end of the merge function:

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)

Confirm that this function works by writing the following:

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)
}

You should see the following console output:

1
1
2
3
3
4
4
5
5
5
6
6
7
7
7
8