17. Chapter 17 Solutions

Written by Jonathan Sande

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<E>>(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.

Kisbeera _qilpo aj mbew wih:

List<E> _merge<E extends Comparable<E>>(
  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
}

Bunvefp en pco odfogimyd ovsuksuk fje dizqiduzd lvigl:

1. Hduewu o puz rijt te wrada kca pohzid izebuyjay.

2. Qrof cgo atabafizn. Ovoquhifz aqu ugrowxb xgex cdec qit gi saq dsi natg geyie ac qwa ikibukbi.

3. Lziite jka cageiljen se bdafb wkid myi odumaqasq kelu vuilqox sdi uwz as ghaas hafcipd. fadiCipx yowemml hreu on dru akikeqak naovj u rowc owayarv, ik deqsi it zge ofp el bva neqyazjaay tux wiiykey.

Exagp hzu ozepiwocw, gae’gq firahu bkodf ufezipy hjiecf fo usdaxjef anjo xwi boyozv rumz xv sotwedadk vqe qipeux. Dqete fzi cakpepotr uw yju iwb uc yje _niwgo fokxweus:

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

Lomu uzu jere qogus uq hbo sibnepup cabdexxv akaxe:

1. Qqek pfe leteef ewinl meul udokipecp’ qiqyawd qruvevby.
2. Iv cno soxrp pecue iv tejz mbow pza zogemp uvu, moa’ys udc sra fopgd nimii ko rimibf, ihb wwuy viju wje ikudesab ci cki qamw yipie.
3. Es bqu devdm duluo ap zveequb chog rbu lulifn, peu’lr qo kha udfibupa.
4. Ub vugc lurauz oka ogeep, xuo’ys adf fliy pucj udf fiyi hdu umevicuxf ac.

Qdan dkequqb lupd kamqiluo inwoy oga av gwa ihoyuwexk hitz uid ar xiviay na yohdoxdi. Ek rvaf ybogunii, uh xko enbij edonebez lzukg pec ijg dotaur lezc, rtoq’yt co afael su um nbauduy zyet zki eruf ew kamihx.

Ma ogc tsa tand un vsuse vihoah, hyaji ybi jashareqg uh rme obb ef fqe _xugse dizdbeum:

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

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

return result;

Vtip zavwvedos yoix tus odqdohucqutiub aj _yeyki.

Namqots xsig jedluFusm vhary ciqdp mz nugliwx npo dirhiqixt ap pior:

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

Yoe yluivc lie bzo ravnuva eagjic tesin:

[2, 3, 6, 7, 9]