Week 01: Foundations (Lab)

Michael T. Gastner

2026-01-08

Intro

Learning Objectives

By the end of this lab, you should be able to:

  1. Understand and implement merge sort, including its pseudocode and C++ implementation.
  2. Submit C++ programs to Gradescope and analyze the autograder’s feedback.
  3. Develop a recursive implementation of insertion sort, reinforcing concepts of recursion in algorithm design.
  4. Compare the running times of algorithms.

Overview of Lab Activities

Upload solutions for the following activities to xSITe or Gradescope:

  1. Merge Sort—Fill in the Gaps
    Complete a partially pre-filled diagram of the merge sort algorithm.
  2. Testing the Gradescope C++ Autograder
    1. Upload and test the provided merge sort code.
    2. Write and upload a basic “Hello, World!” program.
  3. Recursive Implementation of Insertion Sort
    1. Write the Pseudocode.
    2. Implement it as a C++ program.
  4. Comparing Running Times
    Run a provided C++ program and interpret a plot of running time versus input size.

None of today’s activities will be graded, but they will serve as practice for future lab activities. Upload solutions to familiarize yourself with the submission process.

Recap: Merge Sort

Recap: Merge Sort

URL: https://www.youtube.com/watch?v=NwH1d1YWHtE

Pseudocode for Merge Sort

Note that the video and our textbook Cormen et al. (2022) adopt 1-based indexing. Here is the pseudocode for merge sort for 0-based indexing, as used by https://apps.michael-gastner.com/merge-sort/:

Merge Sort: A Divide-and-Conquer Algorithm

Merge sort is a divide-and-conquer algorithm because it breaks a problem into smaller, related subproblems and then combines these solutions to solve the original problem.

Divide-and-conquer algorithms are recursive. For instance, the sort procedure in the pseudocode on the previous slide calls itself in lines 6 and 7.

Example: Merge Sort Applied to an Array

The example on the right illustrates the merge sort algorithm applied to a numeric array, modeled after Figure 2.4 in Cormen et al. (2022).

Italicized numbers indicate the sequence in which the sort() and merge() procedures are invoked, starting with the initial call to sort(a, 0, 7).

Exercise 1: Merge Sort—Fill in the Gaps

Download the image on the right from GitHub Pages in PNG or PDF format. Adopting the pattern from the example on the previous page, complete the following tasks:

  1. Label the arrows with numbers indicating the sequence of the sort() and merge() procedure calls.
  2. Fill in the correct values in the empty boxes.

You may use any drawing tool, such as Annotely. When finished, upload the completed image (e.g., as a screenshot) to xSITe (Dropbox → Week 01 Lab Exercise 1: Merge Sort—Fill in the Gaps).

Solution: Merge Sort—Fill in the Gaps

  1. Note that the order of calls to the sort() and merge() procedures is identical to the previous example. This order depends only on the length of the array, not on its values.
  2. The correct values are the sorted subarrays, comprising all values that point to the subarray from above.

Merge Sort in C++

C++ Implementation Overview

As with the insertion sort implementation discussed in the lecture, we split the merge sort implementation into multiple files to enhance code readability and maintainability. You can download the complete code as a ZIP archive.

main.cpp
Entry point of the program
import_numbers_from_file.cpp and import_numbers_from_file.h
Functions to import numbers from a file, one number per line
merge_sort.cpp and merge_sort.h
Implementation of the merge() and sort() procedures
makefile
File to compile the program using make

Merge Sort’s main.cpp (Part 1)

The first part of main.cpp includes the headers, defines exit codes, and validates command-line arguments:

#include <cstdlib>
#include <exception>
#include <iostream>
#include <string>
#include <vector>

#include "import_numbers_from_file.h"
#include "merge_sort.h"

int main(int argc, char *argv[]) {
  enum ExitCode {
    ok = EXIT_SUCCESS,
    fail = 1,
    usage = 2,
    io = 3,
    bad_input = 4,
  };

  if (argc != 2) {
    std::cerr << "Usage: " << argv[0] << " <filename>\n";
    return usage;
  }

Merge Sort’s main.cpp (Part 2)

The second part reads numbers from a file, sorts them using merge sort, and prints the result:

  try {
    const std::string filename = argv[1];
    std::vector<int> a = importNumbersFromFile(filename);
    if (!a.empty()) {
      mergeSort(a, 0, a.size() - 1);
    }

    for (std::size_t k = 0; k < a.size(); ++k) {
      if (k > 0) {
        std::cout << ", ";
      }
      std::cout << a[k];
    }
    std::cout << '\n';
    return ok;
  } catch (const std::runtime_error &ex) {
    std::cerr << "Error: " << ex.what() << "\n";
    return io;
  } catch (const std::exception &ex) {
    std::cerr << "Error: " << ex.what() << "\n";
    return bad_input;
  }
}

merge_sort.cpp: The merge() Function (Part 1)

The merge() function creates temporary arrays and copies elements:

#include "merge_sort.h"

#include <cstddef>
#include <vector>

static void merge(std::vector<int> &a, std::size_t l, std::size_t m,
                  std::size_t r) {
  const std::size_t n_left = m - l + 1;
  const std::size_t n_right = r - m;
  std::vector<int> left(n_left);
  std::vector<int> right(n_right);
  for (std::size_t j = 0; j < n_left; ++j) {
    left[j] = a[l + j];
  }
  for (std::size_t k = 0; k < n_right; ++k) {
    right[k] = a[m + 1 + k];
  }
  std::size_t i = l;
  std::size_t j = 0;
  std::size_t k = 0;

merge_sort.cpp: The merge() Function (Part 2)

The function then merges the sorted subarrays back into the original array:

  while (j < n_left && k < n_right) {
    if (left[j] <= right[k]) {
      a[i] = left[j];
      ++j;
    } else {
      a[i] = right[k];
      ++k;
    }
    ++i;
  }
  while (j < n_left) {
    a[i] = left[j];
    ++i;
    ++j;
  }
  while (k < n_right) {
    a[i] = right[k];
    ++i;
    ++k;
  }
}

merge_sort.cpp: The mergeSort() Function

The mergeSort() function recursively divides the array and calls merge():

void mergeSort(std::vector<int> &a, std::size_t l, std::size_t r) {
  if (l >= r) {
    return;
  }
  const std::size_t m = l + (r - l) / 2;
  mergeSort(a, l, m);
  mergeSort(a, m + 1, r);
  merge(a, l, m, r);
}

Gradescope

Exercise 2a: Testing Gradescope (Merge Sort)

To prepare for future assignments, navigate to the Dropbox folder “Week 01 Lab Exercise 2a: Gradescope Demo—Merge Sort” on xSITe. Download the files as instructed in the assignment. Note that this is a practice assignment and will not be graded.

For simplicity, the solution file merge_sort.cpp is provided in the ZIP archive you downloaded earlier.

Upload the sample solution to Gradescope and review the autograder’s feedback. You can resubmit code as often as needed to familiarize yourself with the submission process. You may want to intentionally introduce an error to observe how the autograder responds.

Exercise 2b: Testing Gradescope (“Hello, World!”)

Write a C++ program, consisting of a single file titled hello_world.cpp that prints “Hello, World!”—exactly these 13 characters, followed by a newline character—to the stdout console. Compile the code using makefile provided in the ZIP archive.

A template for hello_world.cpp is also provided in the ZIP archive. This template won’t print anything. Your task is to update the file.

Follow the instructions in the Dropbox folder “Week 01 Lab Exercise 2b: Gradescope Demo—Hello, World!” on xSITe to prepare your submission. Again, this is a practice assignment and will not be graded.

Solution: “Hello, World!” in C++

You might need to scroll down to view the entire code:

#include <cstdlib>
#include <iostream>

int main() {
  std::cout << "Hello, World!\n";
  return EXIT_SUCCESS;
}

Recursive Insertion Sort

Exercise 3a: Recursive Insertion Sort—Pseudocode

The lecture introduced insertion sort as the non-recursive algorithm shown below.

However, insertion sort can also be implemented as a recursive algorithm. To sort a[0..n], recursively sort the subarray a[0..(n-1)] and then insert a[n] into the sorted subarray. Write pseudocode for this recursive version. Submit your solution (e.g., a photo of your handwritten notes) to xSITe (Dropbox \(\rightarrow\) Pseudocode of Recursive Insertion Sort).

Sample Solution: Pseudocode for Recursive Insertion Sort

Exercise 3b: Recursive Insertion Sort in C++

Implement insertion sort in C++ as a recursive function. Your implementation should be contained in a file named recursive_insertion_sort.cpp. A template file, together with other utilities for compilation are provided in this ZIP archive.

Upload your solution to Gradescope. Detailed instructions are provided on xSITe (Dropbox \(\rightarrow\) Week 01 Lab Exercise 3b: Gradescope—Recursive Insertion Sort in C++).

Sample Solution: Recursive Insertion Sort in C++

#include "recursive_insertion_sort.h"

#include <cstddef>
#include <vector>

// This function sorts the input vector of integers in ascending order in place
// using the insertion sort algorithm. It adopts a recursive approach (i.e.,
// it calls itself).
void recursiveInsertionSort(std::vector<int> &a, std::size_t n) {
  // Base case: If the array has one or zero elements, it is already sorted
  if (n <= 1) {
    return;
  }

  // Insert a[n - 1] into the sorted subvector a[0:(n-2)]
  recursiveInsertionSort(a, n - 1);

  const int active_key = a[n - 1];
  std::size_t h = n - 1;
  while (h > 0 && a[h - 1] > active_key) {
    a[h] = a[h - 1];
    --h;
  }
  a[h] = active_key;
}

Comparing Running Times

Comparing Running Times

We have studied three implementations for sorting an array of numbers:

  • Non-recursive insertion sort
  • Recursive insertion sort
  • Merge sort

Which algorithm is best in practice? The choice depends on the size of the input array and the relative efficiency of the algorithms, particularly in terms of running time and memory usage.

To evaluate their performance, we will compare the running times of the three algorithms for sorting arrays of various sizes. Using the std::chrono library, we can measure these running times with a high-resolution clock for precise time measurement.

C++ Code for Comparing Running Times

Code for running-time measurements is available as a ZIP archive, containing the following files:

  • Entry point of the program: main.cpp
  • Sorting algorithms:
    • insertion_sort.cpp and insertion_sort.h
    • recursive_insertion_sort.cpp and recursive_insertion_sort.h
    • merge_sort.cpp and merge_sort.h
  • Utilities for plotting: vega_lite_plot.cpp, vega_lite_plot.h, and nlohmann_json.h
  • File to compile the project: makefile

Explanation of the C++ Program

When you execute make run, the program generates arrays of random numbers and sorts them using non-recursive insertion sort, recursive insertion sort, and merge sort. The running times for arrays of different sizes are measured and stored in a JSON file. You can visualize the data by opening the generated file vega_lite_plot.html in a web browser. A sample run is shown on the following page.

Sample Run of the C++ Program

Array Size Insertion Sort (µs) Recursive Insertion Sort (µs)  Merge Sort (µs)
        10                   0                             0                3
        20                   0                             0                7
        50                   2                             3               23
       100                  12                            10               35
       200                  34                            36               72
       500                 206                           237              227
      1000                1050                           847              457
      2000                3325                          3421              893

On my computer, both versions of insertion sort exhibit approximately equal running times. Merge sort is slower on small arrays but faster on larger arrays. The representative plot on the following slide confirms this observation.

Plot of Running Time versus Array Size

Conclusion

Summary of Key Learning Outcomes

  1. Reviewed the merge sort algorithm and its pseudocode. ↪
  2. Explored the multi-file C++ implementation of merge sort. ↪
  3. Submitted C++ programs to Gradescope and interpreted the autograder’s feedback (merge sort and “Hello, World!”). ↪
  4. Developed a recursive insertion sort (pseudocode and C++). ↪
  5. Compared the running times of non-recursive insertion sort, recursive insertion sort, and merge sort. ↪

Outlook

Next week, you will learn to analyze the running times of algorithms and express them using mathematical notation. The lecture and lab will cover sections of Chapters 3 and 4 in Cormen et al. (2022).

References

Cormen, T.H. et al. (2022) Introduction to algorithms. 4th ed. MIT Press.