16.
Merge Sort
Written by Kelvin Lau & Jonathan Sande
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
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:
The merge sort algorithm works as follows. First, split the pile in half. You now have two unsorted piles:
Split those piles again:
You keep splitting until you can’t split anymore. In the end, you’ll have one (sorted!) card in each pile:
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:
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
}
// 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
if (indexA < listA.length) {
result.addAll(listA.getRange(indexA, listA.length));
}
if (indexB < listB.length) {
result.addAll(listB.getRange(indexB, listB.length));
}
return result;
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
}
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);
}
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');
}
Original: [7, 2, 6, 3, 9]
Merge sorted: [2, 3, 3, 6, 7]
Performance
The best, worst and average time complexity of merge sort is quasilinear, or O(n log n), which isn’t too bad.
Challenges
Challenge 1: Mind Merge
Given the following list:
[4, 2, 5, 1, 3]
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.