Merge Sort

Section 26.8 Merge Sort

Now we are ready to return to the algorithm itself. Recall that it looks like this:

MergeSort(list):
  if length of list <= 1:
    return list  // size 0/1 already sorted
  else:
    Split list into leftHalf and rightHalf
    MergeSort(leftHalf)
    MergeSort(rightHalf)
    return Merge(leftHalf, rightHalf)

It is a classic example of a divide-and-conquer algorithm. We divide the work into smaller subproblems, solve each subproblem recursively, and then combine the solutions.

🔗

Implemented in C++ for a vector, it looks like this:

🔗

Listing 26.8.1.

🔗

#include <iostream>
#include <vector>
using namespace std;

#include "vector-helpers.h"

// Other helpers (defined below main)
template<typename T>
void merge(vector<T>& vec, int start, int end, vector<T>& temp);

string spaces(bool add = true, bool remove = false);

// Recursive merge sort function
template<typename T>
void mergeSort(vector<T>& vec, int start, int end, vector<T>& temp) {
    if (start >= end) {
        return; // Base case: 0-1 items are already sorted
    }
    // Debug output
    cout << spaces() << "mergeSort called with start=" << start << ", end=" << end << endl;
    cout << spaces(false) << vectorToString(vec, start, end) << endl;

int mid = (start + end) / 2;
    mergeSort(vec, start, mid, temp);       // Sort left half
    mergeSort(vec, mid + 1, end, temp);     // Sort right half
    merge(vec, start, end, temp);           // Merge the two halves
    
    // Debug output
    cout << spaces(false) << "mergeSort ending with start=" << start << ", end=" << end << endl;
    cout << spaces(false) << vectorToString(vec, start, end) << endl;
    spaces(false, true);
}

// Wrapper function to initiate merge sort
template<typename T>
void mergeSort(vector<T>& vec) {
    // Make temporary vector for merges
    vector<T> temp(vec.size());
    // Do the sort
    mergeSort(vec, 0, vec.size() - 1, temp);
}

int main() {
    vector<int> numbers = {8, 3, 7, 1, 9, 12, 20, 6, 11, 14, 2, 16, 4, 10, 5, 15};
    mergeSort(numbers);
    cout << "Sorted array: " << endl;
    cout << vectorToString(numbers) << endl;
}

// Assumes start/end consists of two sorted halves:
//   [start..mid] and [mid+1..end]
// Temp should be same size as vec. It is a parameter so that later we
//   can reuse the same temp vector across multiple calls to merge
template<typename T>
void merge(vector<T>& vec, int start, int end, vector<T>& temp) {
    int mid = (start + end) / 2;
    int nextLeft = start;
    int nextRight = mid + 1;
    int mergeIndex = start;

int totalItems = end - start + 1;
    for(int i = 0; i < totalItems; ++i) {
        // determine if taking from left or right
        bool takeLeft;
        bool leftEmpty = (nextLeft > mid);
        bool rightEmpty = (nextRight > end);
        if (rightEmpty) {
            takeLeft = true;
        } else if (leftEmpty) {
            takeLeft = false;
        } else if (vec.at(nextLeft) <= vec.at(nextRight)) {
            // items in both, left is smaller
            takeLeft = true;
        } else {
            // items in both, right is smaller
            takeLeft = false;
        }

// take from the chosen side
        if (takeLeft) {
            temp.at(mergeIndex) = vec.at(nextLeft);
            nextLeft++;
        } else {
            temp.at(mergeIndex) = vec.at(nextRight);
            nextRight++;
        }
        mergeIndex++;
    }

// Copy the merged elements back into the original vector
    for (int i = start; i <= end; ++i) {
        vec.at(i) = temp.at(i);
    }
}

// Manage indentation for debug output
string spaces(bool add, bool remove) {
  static string spaces = "";
  if (add) {
      string curSpaces = spaces;
      spaces += " ";
      return curSpaces;
  }
  if (remove) {
      spaces.pop_back();
  }
  return spaces;
}

Note that main calls a wrapper function mergeSort(vector<T>& vec)defined on line 36. It creates a temporary vector and then calls the recursive merge sort function to do the actual sorting. Creating one temporary vector and reusing it across recursive calls is more efficient than creating a new one for each merge.

🔗

The recursive mergeSort function itself only has about 7 lines of real code, half of its shown length is devoted to printing debugging information. That debugging tells us what order the recursive calls happen in and what the vector looks like at each step.

🔗

The debugging information is indented to show the recursive depth at each step. For example, in the portion displayed below, we can see that the first call was to sort the entire list from index 0 to 15. Then the current state of the array is displayed. This call then makes a recursive call to sort the left half from index 0 to 7, which in turn makes a recursive call to sort the left half from index 0 to 3, and so on. Each level of recursion adds an additional level of indentation to the output, making it easier to see the structure of the recursive calls.

🔗

mergeSort called with start=0, end=15
 [8, 3, 7, 1, 9, 12, 6, 20, 11, 14, 2, 16, 4, 10, 5, 15]
 mergeSort called with start=0, end=7
  [8, 3, 7, 1, 9, 12, 6, 20, _, _, _, _, _, _, _, _]
  mergeSort called with start=0, end=3
   [8, 3, 7, 1, _, _, _, _, _, _, _, _, _, _, _, _]
   ...

Due to the way recursion works, we always sort the entire left side of the current range before sorting the right side. When both the left and right sides are sorted, we merge them together.

🔗

Sort 0-15
 Sort 0-7 (left half of 0-15)
  Sort 0-3 (left half of 0-7)
   Sort 0-1 (left half of 0-3)
   Merge 0-1
   Sort 2-3 (right half of 0-3)
   Merge 2-3
  Merge 0-3
  Sort 4-7 (right half of 0-7)
   Sort 4-5 (left half of 4-7)
   ...

To understand the output better, try out this visual interactive tool that demonstrates the process.

🔗

Activity 26.8.1. Merge Sort.

Instructions.

Click "Step" to advance once step or "Play" to run continuously.

🔗

At the top, you can see a description of the current step. On the right, you can see the current call stack.

🔗

Try playing the interactive at a high speed to see the flow of the process. We start by recursing down in the left half until we reach single-item lists. Then we begin merging those single-item lists into sorted two-item lists. After finishing a left half of any given range, we move to the right half and repeat the process on it.This process plays out at each size level (1/2/4/8/16/32...) until the entire list is merged back together in sorted order.

🔗

Merge sort is a stable algorithm as long as we always favor the left element when merging two equal elements. For example, during the merge process, given the two lists:

🔗

Left:  3, 6, 7, 9  Right: 3, 4, 5

We should choose to merge the left 3 first. This will maintain the relative order of equal elements, preserving stability.

🔗

Checkpoint 26.8.1.

We call merge sort on a list with indexes 0-7. Arrange the following blocks in the order of recursive calls that would be made.

🔗

MergeSort(0, 7)
---
MergeSort(0, 3)
---
MergeSort(0, 1)
---
MergeSort(2, 3)
---
MergeSort(4, 7)
---
MergeSort(4, 5)
---
MergeSort(6, 7)

🔗

You have attempted of activities on this page.

🔗

Prev Top Next