You will implement the merge and quick sort algorithm.
Learning Objectives:
- understand how merge sort and quicksort work
- practice recursion
- practice using property-based tests
Real-world application: Given a dataset, the first step of processing is almost always to sort the data. This allows efficient lookups via binary search, but it even makes sequential search significantly faster due to an optimization in modern CPUs called "branch prediction". (See the most upvoted stackoverflow question of all time for details.)
In the real world, you will never implement your own sorting algorithm, and will always use a built-in library routine. The divide-and-conquer strategy used in merge/quick sort turns out to be the most fundamental tool for building your own fast algorithms. Next week (after spring break), we will explore this strategy for massively parallel data analysis of multi-terabyte twitter data. If you take CS148 (graph algorithms), you will explore many more variations of the divide and conquer technique.
Complete the following tasks:
- Fork the sorting repo and enable github actions
- Update the
README.md
file so that the test case badges point to your repo. - Implement the
_merged
,merge_sorted
, andquick_sorted
functions so that all test cases intests/test_main.py
pass. You must implementmerge_sorted
andquick_sorted
recursively. - (optionally)
You can receive 1 point of extra credit for implementing the
quick_sort
function and passing the tests intests/test_ec.py
.
Submit the link to your forked repository on sakai.
You are not allowed to look at another student's github repo.
All other forms of collaboration with other students are encouraged. You may use any other online resources you like to complete this assignment.