16 Chapter 16 Solutions

Solution to Challenge 1

Stepping through the code of mergeSort one line at a time is probably the easiest way to understand what’s happening.

A few strategically placed print statements can also help:

List<E> mergeSort<E extends Comparable<dynamic>>(List<E> list) {
  if (list.length < 2) {
    print('recursion ending:  $list');
    return list;
  } else {
    print('recursion list in: $list');
  }

  final middle = list.length ~/ 2;
  final left = mergeSort(list.sublist(0, middle));
  final right = mergeSort(list.sublist(middle));

  final merged = _merge(left, right);
  print('recursion ending:  merging $left and $right -> $merged');
  return merged;
}

Here’s the output for sorting the list [[4, 2, 5, 1, 3]:

recursion list in: [4, 2, 5, 1, 3]
recursion list in: [4, 2]
recursion ending:  [4]
recursion ending:  [2]
recursion ending:  merging [4] and [2] -> [2, 4]
recursion list in: [5, 1, 3]
recursion ending:  [5]
recursion list in: [1, 3]
recursion ending:  [1]
recursion ending:  [3]
recursion ending:  merging [1] and [3] -> [1, 3]
recursion ending:  merging [5] and [1, 3] -> [1, 3, 5]
recursion ending:  merging [2, 4] and [1, 3, 5] -> [1, 2, 3, 4, 5]

[1, 2, 3, 4, 5]

Solution to Challenge 2

The tricky part of this challenge is the limited capabilities of Iterable. Traditional implementations of merge sort rely on using the indices of a list. Since Iterable types have no notion of indices, though, you’ll make use of their iterator.

Recreate _merge in this way:

List<E> _merge<E extends Comparable<dynamic>>(
  Iterable<E> first,
  Iterable<E> second,
) {
  // 1
  var result = <E>[];

  // 2
  var firstIterator = first.iterator;
  var secondIterator = second.iterator;

  // 3
  var firstHasValue = firstIterator.moveNext();
  var secondHasValue = secondIterator.moveNext();

  // more to come
}

Setting up the algorithm involves the following steps:

1. Create a new list to store the merged iterables.
2. Grab the iterators. Iterators are objects that know how to get the next value in the iterable.
3. Create two variables to keep track of when the iterators have reached the end of their content. moveNext returns true if the iterator found a next element, or false if the end of the collection was reached.

Using the iterators, you’ll decide which element should be appended into the result list by comparing the values. Write the following at the end of the _merge function:

while (firstHasValue && secondHasValue) {
  // 1
  final firstValue = firstIterator.current;
  final secondValue = secondIterator.current;

  // 2
  if (firstValue.compareTo(secondValue) < 0) {
    result.add(firstValue);
    firstHasValue = firstIterator.moveNext();

  // 3
  } else if (firstValue.compareTo(secondValue) > 0) {
    result.add(secondValue);
    secondHasValue = secondIterator.moveNext();

  // 4
  } else {
    result.add(firstValue);
    result.add(secondValue);
    firstHasValue = firstIterator.moveNext();
    secondHasValue = secondIterator.moveNext();
  }
}

// more to come

Here are some notes on the numbered comments above:

1. Grab the values using the current property of your iterators.
2. If the first value is less than the second one, you’ll add the first value to result, and then move the iterator to the next value.
3. If the first value is greater than the second, you’ll do the opposite.
4. If both values are equal, you’ll add them both and move the iterators on.

This process will continue until one of the iterators runs out of values to dispense. In that scenario, if the other iterator still has any values left, they’ll be equal to or greater than the ones in result.

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

if (firstHasValue) {
  do {
    result.add(firstIterator.current);
  } while (firstIterator.moveNext());
}

if (secondHasValue) {
  do {
    result.add(secondIterator.current);
  } while (secondIterator.moveNext());
}

return result;

That completes your new implementation of _merge.

Confirm that mergeSort still works by running the following in main:

final list = [7, 2, 6, 3, 9];
final sorted = mergeSort(list);
print(sorted);

You should see the console output below:

[2, 3, 6, 7, 9]