Merge sort (von Neumann)

Merge sort is entirely different than the sorting algorithms we鈥檝e seen so far, and it represents an important class of algorithms鈥攄ivide-and-conquer algorithms. Divide-and-conquer algorithms work by breaking a problem down into smaller subproblems, solving the subproblems, and then building a complete result from the solved subproblems. Merge sort uses recursion to do this.

Here we implement merge sort in C++.

Additional resources:

• mergeSort.cpp
• Merge_Sort.pdf

Comprehension check:

1. True or false. A single-element vector is sorted by definition.
2. True or false. Merge sort begins by recursively dividing its input into smaller vectors.
3. True or false. The input to the merge function is two unsorted vectors.
4. True or false. Merge sort is not a stable sorting algorithm.
5. Given two input vectors 3, 5, 7 (left) and 1, 8, 9 (right), the merge function would consume elements from these vectors in the sequence right, left, ______, ______, ______, right.

Answers: 蕠丧苾岽壣� / 蕠蔁菨l / 蕠蔁菨l / 菨sl蓯蔁 / 菨sl蓯蔁 / 菨n晒蕠 / 菨n晒蕠

Copyright 漏 2023鈥�2025 Clayton Cafiero

No generative AI was used in producing this material. This was written the old-fashioned way.