跳转至

16 Merge Sort

With a time complexity of O(n log n), merge sort is one of the fastest of the general-purpose sorting algorithms. The idea behind merge sort is to divide and conquer — to break up a big problem into several smaller, easier-to-solve problems and then combine the solutions into a final result. The merge sort mantra is to split first and merge later.

In this chapter, you’ll implement merge sort from scratch. The example below will help you gain an intuitive understanding of how the algorithm works before you write the code.

Example

Assume that you’re given a pile of unsorted playing cards:

7722663399

The merge sort algorithm works as follows. First, split the pile in half. You now have two unsorted piles:

7722663399

Split those piles again:

7722663399

You keep splitting until you can’t split anymore. In the end, you’ll have one (sorted!) card in each pile:

7722663399

Finally, merge the piles in the reverse order in which you split them. During each merge, you put the contents in sorted order. This process is easy because each pile is already sorted:

223377336699

223377336699

2233667799

Do you understand the general idea of how merge sort works now? You’ll build the algorithm with code next.

Implementation

Open up the starter project and create a new lib folder in the root of your project. Then create a new file in lib named merge_sort.dart.

Merging Lists

You’ll start by creating a helper function named _merge. The sole responsibility of this function is to take in two sorted lists and combine them while retaining the sort order. Add the following to merge_sort.dart:

List<E> _merge<E extends Comparable<dynamic>>(
  List<E> listA,
  List<E> listB,
) {

  var indexA = 0;
  var indexB = 0;
  final result = <E>[];

  // more to come
}

indexA and indexB track your progress as you parse through the two lists. The result list will house the merged list that you’re about to make.

Next add the following while loop at the bottom of _merge:

// 1
while (indexA < listA.length && indexB < listB.length) {
  final valueA = listA[indexA];
  final valueB = listB[indexB];
  // 2
  if (valueA.compareTo(valueB) < 0) {
    result.add(valueA);
    indexA += 1;
  } else if (valueA.compareTo(valueB) > 0) {
    result.add(valueB);
    indexB += 1;
  } else {
    // 3
    result.add(valueA);
    result.add(valueB);
    indexA += 1;
    indexB += 1;
  }
}

// more to come

Here’s what’s happening:

  1. Starting from the beginning of listA and listB, you sequentially compare the values. If you’ve reached the end of either list, there’s nothing else to compare.
  2. The smaller of the two values go into the result list.
  3. If the values are equal, they can both be added.

Finally, add the following code to the bottom of _merge:

if (indexA < listA.length) {
  result.addAll(listA.getRange(indexA, listA.length));
}

if (indexB < listB.length) {
  result.addAll(listB.getRange(indexB, listB.length));
}

return result;

The while loop above guaranteed that either left or right is already empty. Since both lists are sorted, this ensures that any leftover elements are greater than or equal to the ones currently in result. In this scenario, you can directly add the rest of the elements without comparison.

Note

getRange is similar to substring except that it doesn’t return a new list. It just returns an iterable pointing to the elements of the current list. No need to spend time creating unnecessary objects.

Splitting

Now it’s time to create the main mergeSort function. Write the following at the top of merge_sort.dart, above the _merge function:

List<E> mergeSort<E extends Comparable<dynamic>>(List<E> list) {
  final middle = list.length ~/ 2;
  final left = list.sublist(0, middle);
  final right = list.sublist(middle);

  // more to come
}

Here, you split the list into halves. Splitting once isn’t enough, though. You need to keep splitting recursively until you can’t split anymore, which is when each subdivision contains just one element.

To do this, replace mergeSort with the following:

List<E> mergeSort<E extends Comparable<dynamic>>(List<E> list) {
  // 1
  if (list.length < 2) return list;
  // 2
  final middle = list.length ~/ 2;
  final left = mergeSort(list.sublist(0, middle));
  final right = mergeSort(list.sublist(middle));
  // 3
  return _merge(left, right);
}

You’ve made a few changes here:

  1. Recursion needs a base case, which you can also think of as an “exit condition.” Here, the base case is when the list only has one element.
  2. You’re now recursively calling mergeSort on the left and right halves of the original list. As soon as you’ve split the list in half, you try to split it again.
  3. Complete the mergeSort function by calling _merge. This will combine the left and right lists that you split above.

You’re finished with the implementation. Time to see it in action.

Testing it Out

Head back to bin/starter.dart to test your merge sort:

import 'package:starter/merge_sort.dart';

void main() {
  final list = [7, 2, 6, 3, 9];
  final sorted = mergeSort(list);
  print('Original: $list');
  print('Merge sorted: $sorted');
}

This outputs:

Original: [7, 2, 6, 3, 9]
Merge sorted: [2, 3, 3, 6, 7]

Nice! It works.

Performance

The best, worst and average time complexity of merge sort is quasilinear, or O(n log n), which isn’t too bad.

If you’re struggling to understand where n log n comes from, think about how the recursion works:

  • As you recurse, you split a single list into two smaller lists. This means a list of size two will need one recursion level, a list of size four will need two levels, a list of size eight will need three levels, and so on. If you had a list of 1,024 elements, it would take ten levels of recursively splitting in two to get down to 1,024 single element lists. In general, if you have a list of size n, the number of recursion levels is log₂(n).
  • The cost of a single recursion is O(n). A single recursion level will merge n elements. It doesn’t matter if there are many small merges or one large one. The number of elements merged will still be n at each level.

This brings the total cost to O(log n) × O(n) = O(n log n).

Bubble sort, selection sort and insertion sort were in-place algorithms since they used swap to move elements around in an existing list. Merge sort, by contrast, allocates additional memory to do its work. How much? There are log₂(n) levels of recursion, and at each level, n elements are used. That makes the total O(n log n) in space complexity. If you’re clever with your bookkeeping, though, you can reduce the memory required to O(n) by discarding the memory that’s not actively being used.

Merge sort is also stable. Elements of the same type retain their relative order after being sorted. This will also be true for radix sort in the next chapter, but not for heapsort and quicksort that you’ll learn about later.

Merge sort is one of the classic sorting algorithms. It’s relatively simple to understand and serves as a great introduction to how divide-and-conquer algorithms work.

Challenges

Challenge 1: Mind Merge

Given the following list:

[4, 2, 5, 1, 3]

Work through the steps merge sort would take. Go slowly enough for your brain to understand what’s happening. You’ll have the easiest time if you use breakpoints in your IDE or add print statements to your code.

Challenge 2: Merge Two Sequences

In this chapter you created a _merge function that merges two sorted lists. The challenge here is to generalize _merge so that it takes two iterables as inputs rather than lists. Here’s the function signature to start off:

List<E> _merge<E extends Comparable<dynamic>>(
  Iterable<E> first,
  Iterable<E> second,
)

Key Points

  • Merge sort is in the category of divide-and-conquer algorithms.
  • Merge sort works by splitting the original list into many individual lists of length one. It then merges pairs of lists into larger and larger sorted lists until the entire collection is sorted.
  • There are many implementations of merge sort, and you can have different performance characteristics depending on the implementation.
  • Merge sort has a time complexity of O(n log n). It does not sort in place, so the space complexity is also O(n log n), but can be O(log n) if optimized.
  • Merge sort is a stable sorting algorithm.