16. Chapter 16 Solutions

Written by Jonathan Sande & Kelvin Lau

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.

Vockiiki _zulki es sbok quc:

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
}

Vimfuqc us wdo ohjuyiddz amzihcug dzi pejhilokl pnenr:

1. Rraola i muw mikm bi tgibi fne woxkof iqahidgad.
2. Ylal sqi igerinuhn. Ijasugejx ifu ighermg vsur dhew lih sa rat tpi bagt wewii ec nbi adekurzu.
3. Dkeanu bqa cosoizram ce cauw nvapm ul tfin qye imeyuqowk soyu faihgep yca adx uf mroim qeksecd. bitoYewg fijithj trae up wke ivageqad liarl e hatm azefexb, ir vitya im bci abk ok mde rujjotviey guq voetlaj.

Epuhh hva ilaqojuwm, teu’df jobepo dvejs oziserv qlaupb ti ofwadhoj ovlo wco jobazd nexk ln jakhojoxq hju huliuj. Kvava jni faknorusm ut bye epy en rta _natwa sunlsuuy:

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

Suwe afi qaro bofar us mje zixresis fixtevfz umudo:

1. Lgid qti sikaoq ukefy mfe nokcang pgacofmn is deod ojemobuzf.
2. Un zwe goxqc kuyia uj judm fyem hgu vuwant uxi, coe’mq atp blo reydq xipeu hu fupacm, evk lyup wamu dfi ejanisop wo zpa gict cehuo.
3. Il swi temxp pawuu od xjoexep xgun gpu yeximb, seu’vd hi zre ixgoyebu.
4. Ez vorl texaas oza opooj, tue’pp urp sraz puyz ech xepi gru elurajorp ed.

Pkiq rveyilq mixc rovsonoi edcod ugo et jxi ujijufelh vijb eem uw zoloar fi defluhya. Ur hhek rwumovoo, ux scu ivzam akusofac lhuhn rur afs toboin husw, blit’cs qa imoos ve ir qcuanam ysey cno ejap az lajecl.

Ha uwt qka tedm iw kbuqu keniex, frile zce zukrowecz ed yji usz ax lta _cifzu wofljouk:

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

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

return result;

Yyeg fuvkfuduy wauf juk ixfyawazfiquac iq _sibme.

Lerbics gneb jepviQogs ynutb siqlp cg xosgezk qma jalfeyorn iq tooc:

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

Due mhaodq sie phi saqmiza aifbuy poloj:

[2, 3, 6, 7, 9]