Sorting: Insertion Sort vs. Merge Sort

Sorting is one of the most-used operations in computer programs, and there are many different sorting algorithms with very different characteristics — some are simple to implement, some are fast on already-sorted data, some trade memory for speed. The right choice depends on what you know about your data and what resources you have.

This programming assignment asks you to implement two classic sorting algorithms: insertion sort (a straightforward iterative approach) and merge sort (a recursive divide-and-conquer approach). Because merge sort works by combining smaller sorted lists, you'll also write a helper function called merge along the way. After implementing all three, you'll see side-by-side graphs comparing operation counts, execution times, and memory usage across lists of varying size.

Files

• main.py — Where you write insertion_sort, merge, and merge_sort. Function signatures are already provided; do not change them. Running this file also prints a small sanity check using each function on a short list.
• sort_unit_tests.py — Correctness tests for each function, including edge cases (empty list, single element, already sorted, reverse-sorted, duplicates). Run these once your sanity check passes.
• sort_full_tests.py — The full performance suite. Runs both sorts on lists of increasing size and plots the results.
• number_generator.py — Helper that builds randomized unsorted lists of floats for testing.

Getting your own copy

You'll work on your own copy of this project on GitHub so you can commit your changes as you go.

1. On the GitHub page for this repository, click the green Use this template button and choose Create a new repository. This creates a fresh copy of the project under your GitHub account.

2. On your new repository's page, click the green Code button and copy the URL.

3. In a terminal on your computer, clone your copy:

   git clone <the URL you copied>
   cd sorting_py
   

4. As you make progress, save your work back to GitHub:

   git add .
   git commit -m "describe what you changed"
   git push
   

Getting updates from the teacher

If your teacher updates the starter project (for example, adds new test cases), you can pull those changes into your own copy. You only need to set this up once:

git remote add upstream https://github.com/christianmiley/sorting_py.git

After that, whenever there are updates to grab:

git fetch upstream
git merge upstream/main

Your own work in main.py won't be touched — the merge just brings in the teacher's changes to the test files.

Setup

This project needs Python 3 and matplotlib (for the graphs at the end of the full suite). Install the dependencies with:

pip install -r requirements.txt

How to run the tests

There are three levels of testing, and you should work through them in order. Each one catches different problems: the sanity check makes sure your functions run at all, the unit tests catch correctness bugs cheaply, and the full suite reveals how the algorithms scale.

1. Sanity check — confirm your functions run on a tiny hand-written example:

   python main.py
   

   This prints the result of each sort on a short list. If the output looks reasonable, move on. If something crashes, fix it before going further.

2. Unit tests — check correctness across edge cases:

   python sort_unit_tests.py
   

   You should see every case pass for insertion_sort, merge, and merge_sort before moving on.

3. Full test suite — run the performance comparison:

   python sort_full_tests.py
   

   This prints per-size operation counts, execution times, and peak memory usage, then opens a window with three graphs comparing the two sorts.