7.6. Merge sort¶

We now turn our attention to using a divide and conquer strategy as a way to improve the performance of sorting algorithms. The first algorithm we will study is the merge sort. Merge sort is a recursive algorithm that continually splits a vector in half. If the vector is empty or has one item, it is sorted by definition (the base case). If the vector has more than one item, we split the vector and recursively invoke a merge sort on both halves. Once the two halves are sorted, the fundamental operation, called a merge, is performed. Merging is the process of taking two smaller sorted vectors and combining them together into a single, sorted, new vector. The following sequence shows the recursive splits and the merge process for our familiar example array.

Merge sort: split, sort, and merge

Card 1: Begin with the original array.

Merge sort splits an array, sorts its left half recursively, then sorts its right half and merges the results.

Merge-sort arrays and their parent-child relationships.

Text description

Tree diagram with 1 visible node.

The root is array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”].

array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”] is a leaf.

Card 2: Split into a four-item left half and a five-item right half.

Because there are 9 elements, the split is an an array of size 4 and and array of size 5. We continue down the left half of the array.

Text description

Tree diagram with 3 visible nodes.

The root is array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”].

array node left with 4 cells [“54”, “26”, “93”, “17”] and array node right with 5 cells [“77”, “31”, “44”, “55”, “20”] are leaves.

Card 3: Split the left half into two pairs.

The left half splits into [54, 26] and [93, 17].

Text description

Tree diagram with 5 visible nodes.

The root is array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”].

array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”] has left child array node left with 4 cells [“54”, “26”, “93”, “17”] and right child array node right with 5 cells [“77”, “31”, “44”, “55”, “20”]. array node left with 4 cells [“54”, “26”, “93”, “17”] has left child array node left_left with 2 cells [“54”, “26”] and right child array node left_right with 2 cells [“93”, “17”].

array node right with 5 cells [“77”, “31”, “44”, “55”, “20”], array node left_left with 2 cells [“54”, “26”], and array node left_right with 2 cells [“93”, “17”] are leaves.

Card 4: Reach the first two base cases.

Each one-item array is already sorted. The parent array will be filled by merging them.

Text description

Tree diagram with 7 visible nodes.

The root is array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”].

array node right with 5 cells [“77”, “31”, “44”, “55”, “20”], array node left_right with 2 cells [“93”, “17”], array node left_left_left with 1 cells [“54”], and array node left_left_right with 1 cells [“26”] are leaves.

Card 5: Merge the first two leaves: compare 54 and 26.

To merge two sorted arrays, write the minimum value to parent position 0, then repeatedly write the minimum remaining value to the next position. The first remaining value in each sorted input is its minimum, so compare those values.

Each write replaces the value already in that parent position.

Text description

Tree diagram with 7 visible nodes.

The root is array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”].

“54” (node left_left_left, cell 0) and “26” (node left_left_right, cell 0) are highlighted.

parent points to merge node left_left, cell 0, value '54'.

Card 6: Move 26; then move the minimum remaining value, 54.

Move 26 to parent position 0. The minimum remaining value is 54, the only value left. Move it to parent position 1.

Text description

Tree diagram with 7 visible nodes.

The root is array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”].

array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”] has left child array node left with 4 cells [“54”, “26”, “93”, “17”] and right child array node right with 5 cells [“77”, “31”, “44”, “55”, “20”]. array node left with 4 cells [“54”, “26”, “93”, “17”] has left child array node left_left with 2 cells [“26”, “26”] and right child array node left_right with 2 cells [“93”, “17”]. array node left_left with 2 cells [“26”, “26”] has left child array node left_left_left with 1 cells [“54”] and right child array node left_left_right with 1 cells [an unused cell].

“26” (node left_left, cell 0) and “54” (node left_left_left, cell 0) are highlighted.

Card 7: Merge the first pair; split the second pair.

Now split the waiting pair [93, 17] into [93] and [17]. These are also sorted base cases.

Text description

Tree diagram with 7 visible nodes.

The root is array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”].

array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”] has left child array node left with 4 cells [“54”, “26”, “93”, “17”] and right child array node right with 5 cells [“77”, “31”, “44”, “55”, “20”]. array node left with 4 cells [“54”, “26”, “93”, “17”] has left child array node left_left with 2 cells [“26”, “54”] and right child array node left_right with 2 cells [“93”, “17”]. array node left_right with 2 cells [“93”, “17”] has left child array node left_right_left with 1 cells [“93”] and right child array node left_right_right with 1 cells [“17”].

array node right with 5 cells [“77”, “31”, “44”, “55”, “20”], array node left_left with 2 cells [“26”, “54”], array node left_right_left with 1 cells [“93”], and array node left_right_right with 1 cells [“17”] are leaves.

“93” (node left_right_left, cell 0) and “17” (node left_right_right, cell 0) are highlighted.

Card 8: Both pairs in the left half are sorted.

Merge [93] and [17] by moving 17 before 93. The left half now has two sorted child arrays, [26, 54] and [17, 93], ready to merge. The right half still waits.

Text description

Tree diagram with 5 visible nodes.

The root is array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”].

array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”] has left child array node left with 4 cells [“54”, “26”, “93”, “17”] and right child array node right with 5 cells [“77”, “31”, “44”, “55”, “20”]. array node left with 4 cells [“54”, “26”, “93”, “17”] has left child array node left_left with 2 cells [“26”, “54”] and right child array node left_right with 2 cells [“17”, “93”].

array node right with 5 cells [“77”, “31”, “44”, “55”, “20”], array node left_left with 2 cells [“26”, “54”], and array node left_right with 2 cells [“17”, “93”] are leaves.

Card 9: Merge the two sorted pairs: compare 26 and 17.

Compare the first remaining value of each sorted child: 26 and 17. The smaller value, 17, is the value to move to output position 0.

Text description

Tree diagram with 5 visible nodes.

The root is array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”].

array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”] has left child array node left with 4 cells [“54”, “26”, “93”, “17”] and right child array node right with 5 cells [“77”, “31”, “44”, “55”, “20”]. array node left with 4 cells [“54”, “26”, “93”, “17”] has left child array node left_left with 2 cells [“26”, “54”] and right child array node left_right with 2 cells [“17”, “93”].

“26” (node left_left, cell 0) and “17” (node left_right, cell 0) are highlighted.

Card 10: Move 17; compare 26 and 93.

Move 17 to output position 0 and advance in the right input. Since 26 is less than 93 move 26 to parent position 1.

Text description

Tree diagram with 5 visible nodes.

The root is array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”].

array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”] has left child array node left with 4 cells [“17”, “26”, “93”, “17”] and right child array node right with 5 cells [“77”, “31”, “44”, “55”, “20”]. array node left with 4 cells [“17”, “26”, “93”, “17”] has left child array node left_left with 2 cells [“26”, “54”] and right child array node left_right with 2 cells [an unused cell, “93”].

array node right with 5 cells [“77”, “31”, “44”, “55”, “20”], array node left_left with 2 cells [“26”, “54”], and array node left_right with 2 cells [an unused cell, “93”] are leaves.

“17” (node left, cell 0), “26” (node left_left, cell 0), and “93” (node left_right, cell 1) are highlighted.

Card 11: Move 26; compare 54 and 93.

Move 26 to output position 1 and advance in the left input. Compare 54 with 93. Move 54 to position 2 because it is smaller.

Text description

Tree diagram with 5 visible nodes.

The root is array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”].

array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”] has left child array node left with 4 cells [“17”, “26”, “93”, “17”] and right child array node right with 5 cells [“77”, “31”, “44”, “55”, “20”]. array node left with 4 cells [“17”, “26”, “93”, “17”] has left child array node left_left with 2 cells [an unused cell, “54”] and right child array node left_right with 2 cells [an unused cell, “93”].

array node right with 5 cells [“77”, “31”, “44”, “55”, “20”], array node left_left with 2 cells [an unused cell, “54”], and array node left_right with 2 cells [an unused cell, “93”] are leaves.

“26” (node left, cell 1), “54” (node left_left, cell 1), and “93” (node left_right, cell 1) are highlighted.

Card 12: Move 54; the left input is exhausted.

Move 54 to output position 2. The left input is now empty, so no further comparison is needed. Move the remaining 93 from the right input to output position 3.

Text description

Tree diagram with 5 visible nodes.

The root is array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”].

array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”] has left child array node left with 4 cells [“17”, “26”, “54”, “17”] and right child array node right with 5 cells [“77”, “31”, “44”, “55”, “20”]. array node left with 4 cells [“17”, “26”, “54”, “17”] has left child array node left_left with 2 cells [an unused cell, an unused cell] and right child array node left_right with 2 cells [an unused cell, “93”].

array node right with 5 cells [“77”, “31”, “44”, “55”, “20”], array node left_left with 2 cells [an unused cell, an unused cell], and array node left_right with 2 cells [an unused cell, “93”] are leaves.

“54” (node left, cell 2) and “93” (node left_right, cell 1) are highlighted.

Card 13: The left half is sorted.

Copying 93 to position 3 completes the left half of the array.

Text description

Tree diagram with 3 visible nodes.

The root is array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”].

array node left with 4 cells [“17”, “26”, “54”, “93”] and array node right with 5 cells [“77”, “31”, “44”, “55”, “20”] are leaves.

Card 14: Split the right half.

Split the right half into [77, 31] and [44, 55, 20]. The lengths differ by one, as in the initial split.

Text description

Tree diagram with 5 visible nodes.

The root is array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”].

array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”] has left child array node left with 4 cells [“17”, “26”, “54”, “93”] and right child array node right with 5 cells [“77”, “31”, “44”, “55”, “20”]. array node right with 5 cells [“77”, “31”, “44”, “55”, “20”] has left child array node right_left with 2 cells [“77”, “31”] and right child array node right_right with 3 cells [“44”, “55”, “20”].

array node left with 4 cells [“17”, “26”, “54”, “93”], array node right_left with 2 cells [“77”, “31”], and array node right_right with 3 cells [“44”, “55”, “20”] are leaves.

Card 15: Sort the right pair; split the remaining three items.

The same base-case splits and merge sort [77, 31] into [31, 77]. We omit those repeated intermediate cards.

Split [44, 55, 20] into [44] and [55, 20]. The one-item array [44] is sorted; the other child still needs splitting.

Text description

Tree diagram with 7 visible nodes.

The root is array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”].

array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”] has left child array node left with 4 cells [“17”, “26”, “54”, “93”] and right child array node right with 5 cells [“77”, “31”, “44”, “55”, “20”]. array node right with 5 cells [“77”, “31”, “44”, “55”, “20”] has left child array node right_left with 2 cells [“31”, “77”] and right child array node right_right with 3 cells [“44”, “55”, “20”]. array node right_right with 3 cells [“44”, “55”, “20”] has left child array node right_right_left with 1 cells [“44”] and right child array node right_right_right with 2 cells [“55”, “20”].

array node left with 4 cells [“17”, “26”, “54”, “93”], array node right_left with 2 cells [“31”, “77”], array node right_right_left with 1 cells [“44”], and array node right_right_right with 2 cells [“55”, “20”] are leaves.

Card 16: Combine the three-item branch.

Merge [55] and [20] into [20, 55], then merge that result with [44] to obtain [20, 44, 55]. These merges follow the same front-value comparisons shown earlier, so we summarize them.

The sorted arrays are ready to merge.

Text description

Tree diagram with 5 visible nodes.

The root is array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”].

array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”] has left child array node left with 4 cells [“17”, “26”, “54”, “93”] and right child array node right with 5 cells [“77”, “31”, “44”, “55”, “20”]. array node right with 5 cells [“77”, “31”, “44”, “55”, “20”] has left child array node right_left with 2 cells [“31”, “77”] and right child array node right_right with 3 cells [“20”, “44”, “55”].

array node left with 4 cells [“17”, “26”, “54”, “93”], array node right_left with 2 cells [“31”, “77”], and array node right_right with 3 cells [“20”, “44”, “55”] are leaves.

Card 17: The right half is sorted.

Merge [31, 77] and [20, 44, 55] to obtain [20, 31, 44, 55, 77]. Both halves of the original array are now sorted and ready for the final merge.

Text description

Tree diagram with 3 visible nodes.

The root is array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”].

array node left with 4 cells [“17”, “26”, “54”, “93”] and array node right with 5 cells [“20”, “31”, “44”, “55”, “77”] are leaves.

Card 18: Begin the final merge.

Merge the two sorted halves into the root array. First compare 17 and 20; choose 17 for root position 0. Continue writing the smaller front value to the next root position, just as in the detailed merge of the left half.

Text description

Tree diagram with 3 visible nodes.

The root is array node root with 9 cells [“54”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”].

array node left with 4 cells [“17”, “26”, “54”, “93”] and array node right with 5 cells [“20”, “31”, “44”, “55”, “77”] are leaves.

“17” (node left, cell 0) and “20” (node right, cell 0) are highlighted.

Card 19: Move 17; compare 26 and 20.

Move 17 from left position 0 to parent position 0. Its source cell is now empty. Compare the remaining front values, 26 and 20; choose 20 next.

Text description

Tree diagram with 3 visible nodes.

The root is array node root with 9 cells [“17”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”].

array node root with 9 cells [“17”, “26”, “93”, “17”, “77”, “31”, “44”, “55”, “20”] has left child array node left with 4 cells [an unused cell, “26”, “54”, “93”] and right child array node right with 5 cells [“20”, “31”, “44”, “55”, “77”].

array node left with 4 cells [an unused cell, “26”, “54”, “93”] and array node right with 5 cells [“20”, “31”, “44”, “55”, “77”] are leaves.

“26” (node left, cell 1), “20” (node right, cell 0), and “17” (node root, cell 0) are highlighted.

Card 20: Move 20; compare 26 and 31.

Move 20 from right position 0 to parent position 1. Its source cell is now empty. Compare 26 and 31; choose 26 for the next parent position.

Text description

Tree diagram with 3 visible nodes.

The root is array node root with 9 cells [“17”, “20”, “93”, “17”, “77”, “31”, “44”, “55”, “20”].

array node root with 9 cells [“17”, “20”, “93”, “17”, “77”, “31”, “44”, “55”, “20”] has left child array node left with 4 cells [an unused cell, “26”, “54”, “93”] and right child array node right with 5 cells [an unused cell, “31”, “44”, “55”, “77”].

array node left with 4 cells [an unused cell, “26”, “54”, “93”] and array node right with 5 cells [an unused cell, “31”, “44”, “55”, “77”] are leaves.

“26” (node left, cell 1), “31” (node right, cell 1), and “20” (node root, cell 1) are highlighted.

Card 21: Move 26; compare 54 and 31.

Move 26 from left position 1 to parent position 2. Its source cell is now empty. Compare 54 and 31; choose 31 for the next parent position.

Text description

Tree diagram with 3 visible nodes.

The root is array node root with 9 cells [“17”, “20”, “26”, “17”, “77”, “31”, “44”, “55”, “20”].

array node root with 9 cells [“17”, “20”, “26”, “17”, “77”, “31”, “44”, “55”, “20”] has left child array node left with 4 cells [an unused cell, an unused cell, “54”, “93”] and right child array node right with 5 cells [an unused cell, “31”, “44”, “55”, “77”].

array node left with 4 cells [an unused cell, an unused cell, “54”, “93”] and array node right with 5 cells [an unused cell, “31”, “44”, “55”, “77”] are leaves.

“54” (node left, cell 2), “31” (node right, cell 1), and “26” (node root, cell 2) are highlighted.

Card 22: Move 31; compare 54 and 44.

Move 31 from right position 1 to parent position 3. Its source cell is now empty. Compare 54 and 44; choose 44 for the next parent position.

Text description

Tree diagram with 3 visible nodes.

The root is array node root with 9 cells [“17”, “20”, “26”, “31”, “77”, “31”, “44”, “55”, “20”].

array node root with 9 cells [“17”, “20”, “26”, “31”, “77”, “31”, “44”, “55”, “20”] has left child array node left with 4 cells [an unused cell, an unused cell, “54”, “93”] and right child array node right with 5 cells [an unused cell, an unused cell, “44”, “55”, “77”].

array node left with 4 cells [an unused cell, an unused cell, “54”, “93”] and array node right with 5 cells [an unused cell, an unused cell, “44”, “55”, “77”] are leaves.

“54” (node left, cell 2), “44” (node right, cell 2), and “31” (node root, cell 3) are highlighted.

Card 23: Move 44; compare 54 and 55.

Move 44 from right position 2 to parent position 4. Its source cell is now empty. Compare 54 and 55; choose 54 for the next parent position.

Text description

Tree diagram with 3 visible nodes.

The root is array node root with 9 cells [“17”, “20”, “26”, “31”, “44”, “31”, “44”, “55”, “20”].

array node root with 9 cells [“17”, “20”, “26”, “31”, “44”, “31”, “44”, “55”, “20”] has left child array node left with 4 cells [an unused cell, an unused cell, “54”, “93”] and right child array node right with 5 cells [an unused cell, an unused cell, an unused cell, “55”, “77”].

array node left with 4 cells [an unused cell, an unused cell, “54”, “93”] and array node right with 5 cells [an unused cell, an unused cell, an unused cell, “55”, “77”] are leaves.

“54” (node left, cell 2), “55” (node right, cell 3), and “44” (node root, cell 4) are highlighted.

Card 24: Move 54; compare 93 and 55.

Move 54 from left position 2 to parent position 5. Its source cell is now empty. Compare 93 and 55; choose 55 for the next parent position.

Text description

Tree diagram with 3 visible nodes.

The root is array node root with 9 cells [“17”, “20”, “26”, “31”, “44”, “54”, “44”, “55”, “20”].

array node root with 9 cells [“17”, “20”, “26”, “31”, “44”, “54”, “44”, “55”, “20”] has left child array node left with 4 cells [an unused cell, an unused cell, an unused cell, “93”] and right child array node right with 5 cells [an unused cell, an unused cell, an unused cell, “55”, “77”].

array node left with 4 cells [an unused cell, an unused cell, an unused cell, “93”] and array node right with 5 cells [an unused cell, an unused cell, an unused cell, “55”, “77”] are leaves.

“93” (node left, cell 3), “55” (node right, cell 3), and “54” (node root, cell 5) are highlighted.

Card 25: Move 55; compare 93 and 77.

Move 55 from right position 3 to parent position 6. Its source cell is now empty. Compare 93 and 77; choose 77 for the next parent position.

Text description

Tree diagram with 3 visible nodes.

The root is array node root with 9 cells [“17”, “20”, “26”, “31”, “44”, “54”, “55”, “55”, “20”].

array node root with 9 cells [“17”, “20”, “26”, “31”, “44”, “54”, “55”, “55”, “20”] has left child array node left with 4 cells [an unused cell, an unused cell, an unused cell, “93”] and right child array node right with 5 cells [an unused cell, an unused cell, an unused cell, an unused cell, “77”].

array node left with 4 cells [an unused cell, an unused cell, an unused cell, “93”] and array node right with 5 cells [an unused cell, an unused cell, an unused cell, an unused cell, “77”] are leaves.

“93” (node left, cell 3), “77” (node right, cell 4), and “55” (node root, cell 6) are highlighted.

Card 26: Move 77; the right input is exhausted.

Move 77 from right position 4 to parent position 7. Its source cell is now empty. The right input is exhausted. Move the only remaining value, 93, to parent position 8; no further comparison is needed.

Text description

Tree diagram with 3 visible nodes.

The root is array node root with 9 cells [“17”, “20”, “26”, “31”, “44”, “54”, “55”, “77”, “20”].

array node root with 9 cells [“17”, “20”, “26”, “31”, “44”, “54”, “55”, “77”, “20”] has left child array node left with 4 cells [an unused cell, an unused cell, an unused cell, “93”] and right child array node right with 5 cells [an unused cell, an unused cell, an unused cell, an unused cell, an unused cell].

array node left with 4 cells [an unused cell, an unused cell, an unused cell, “93”] and array node right with 5 cells [an unused cell, an unused cell, an unused cell, an unused cell, an unused cell] are leaves.

“93” (node left, cell 3) and “77” (node root, cell 7) are highlighted.

Card 27: Move 93; both inputs are exhausted.

Move 93 from left position 3 to parent position 8. Its source cell is now empty. Both input arrays are now empty. Every value has moved into the parent.

Text description

Tree diagram with 3 visible nodes.

The root is array node root with 9 cells [“17”, “20”, “26”, “31”, “44”, “54”, “55”, “77”, “93”].

array node root with 9 cells [“17”, “20”, “26”, “31”, “44”, “54”, “55”, “77”, “93”] has left child array node left with 4 cells [an unused cell, an unused cell, an unused cell, an unused cell] and right child array node right with 5 cells [an unused cell, an unused cell, an unused cell, an unused cell, an unused cell].

array node left with 4 cells [an unused cell, an unused cell, an unused cell, an unused cell] and array node right with 5 cells [an unused cell, an unused cell, an unused cell, an unused cell, an unused cell] are leaves.

“93” (node root, cell 8) is highlighted.

Card 28: The final merge completes the sorted array.

Every item is now in order.

Text description

Tree diagram with 3 visible nodes.

The root is array node root with 9 cells [“17”, “20”, “26”, “31”, “44”, “54”, “55”, “77”, “93”].

Merge Sort

The merge_sort function begins by checking the base case. If the length of the vector is less than or equal to one, then we already have a sorted vector and no more processing is needed. If the length is greater than one, then we extract the left and right halves. It is important to note that the vector may not have an even number of items. That does not matter, as the lengths will differ by at most one.

Once the merge_sort function is invoked on the left half and the right half (lines 23-24), it is assumed they are sorted. The rest of the function is responsible for merging the two smaller sorted vectors into a larger sorted vector. Notice that the merge operation places the items back into the original vector (data) one at a time by repeatedly taking the smallest item from the sorted vectors.

The print function shows the vector contents at the start of each invocation. There is also a print call at the end to show the merging process. The output shows the result of executing the function on our example vector.

Note that the vector with 44, 55, and 20 will not divide evenly. The first split gives [44] and the second gives [55,20]. It is easy to see how the splitting process eventually yields a vector that can be immediately merged with other sorted vectors.

Run It

The Merge Sort

 1#include <iostream>
 2#include <string>
 3#include <vector>
 4using std::cout;
 5using std::vector;
 6
 7void print(const vector<int>& data) {
 8   for (const auto& value: data) {
 9      cout << value << ' ';
10   }
11   cout << '\n';
12}
13
14vector<int> merge_sort(vector<int> data) {
15   cout << "Splitting ";
16   print(data);
17   if (data.size() > 1) {
18      int mid = data.size() / 2;
19      // split data into 2 halves
20      vector<int> left(data.begin(),data.begin()+mid);
21      vector<int> right(data.begin()+mid,data.end());
22
23      left = merge_sort(left);
24      right = merge_sort(right);
25
26      int i = 0, j = 0, k = 0;
27      while (i < int(left.size()) && j < int(right.size())) {
28         if(left[i] < right[j]) {
29            data[k] = left[i];
30            ++i;
31         } else {
32            data[k] = right[j];
33            ++j;
34         }
35         ++k;
36      }
37      while(i < int(left.size())) {
38         data[k] = left[i];
39         ++i;
40         ++k;
41      }
42      while(j < int(right.size())) {
43         data[k] = right[j];
44         ++j;
45         ++k;
46      }
47   }
48   cout << "Merging ";
49   print(data);
50
51   return data;
52}
53
54int main() {
55  vector<int> data = {54, 26, 93, 17, 77, 31, 44, 55, 20};
56  print(merge_sort(data));
57  return 0;
58}

In the following animations, purple marks a range being split, teal marks the range being merged, yellow marks the target slot currently filled, and gray marks merged ranges.

Average case

Best case

Worst case

7.6.1. Merge sort analysis¶

In order to analyze the merge_sort function, we need to consider the two distinct processes that make up its implementation. First, the vector is split into halves. We already computed (in a binary search) that we can divide a vector in half \(\log n\) times where n is the length of the vector. The second process is the merge. Each item in the vector will eventually be processed and placed on the sorted vector. So the merge operation which results in a vector of size n requires n operations. The result of this analysis is that \(\log n\) splits, each of which costs \(n\) for a total of \(n\log n\) operations. A merge sort is an \(O(n \cdot log n)\) algorithm and even better, it is also \(\Omega(n \cdot log n)\) in the worst case.

Recall that the slicing operator is \(O(k)\) where k is the size of the slice. In order to guarantee that merge_sort will be \(O(n \cdot log n)\) we will need to remove the slice operator. Again, this is possible if we simply pass the starting and ending indices along with the vector when we make the recursive call. We leave this as an exercise.

It is important to notice that the merge_sort function requires extra space to hold the two halves as they are extracted with the slicing operations. This additional space can be a critical factor if the vector is large and can make this sort problematic when working on large data sets.

Self Check

Given the following list of numbers: [21, 1, 26, 45, 29, 28, 2, 9, 16, 49, 39, 27, 43, 34, 46, 40] which answer illustrates the list to be sorted after 3 recursive calls to mergesort?

[16, 49, 39, 27, 43, 34, 46, 40]

This is the second half of the list.

[21,1]

Yes, mergesort will continue to recursively move toward the beginning of the list until it hits a base case.

[21, 1, 26, 45]

Remember mergesort doesn't work on the right half of the list until the left half is completely sorted.

[21]

This is the list after 4 recursive calls

Given the following list of numbers: [21, 1, 26, 45, 29, 28, 2, 9, 16, 49, 39, 27, 43, 34, 46, 40] which answer illustrates the first two lists to be merged?

[21, 1] and [26, 45]

The first two lists merged will be base case lists, we have not yet reached a base case.

[[1, 2, 9, 21, 26, 28, 29, 45] and [16, 27, 34, 39, 40, 43, 46, 49]

These will be the last two lists merged

[21] and [1]

The lists [21] and [1] are the first two base cases encountered by mergesort and will therefore be the first two lists merged.

[9] and [16]

Although 9 and 16 are next to each other they are in different halves of the list starting with the first split.

More to Explore