Reading 04: Merge Sort and Quick Sort

Readings

The readings for Monday, September 19 are:

  1. Data Structures and Other Objects Using C++:

    • Chapter 9, 13.2, 13.4

  2. Sorting Algorithms Animations

TL;DR

The focus of the reading is on using divide and conquer in merge sort and quick sort.

Alternative

If you do not have the primary textbook, you can use the following free alternative texts instead:

  1. Data Structures & Algorithm Analysis

    • 7.4 Mergesort
    • 7.5 Quicksort
    • 7.8 An Empirical Comparison of Sorting Algorithms

  2. Open Data Structures

  3. Algorithms

Questions

Once you have completed the readings, answer the following questions in the reading04/README.md file in your assignments repository:

  1. merge sort is the prototypical example of a divide and conquer algorithm. Explain what happens during the divide portion of the algorithm and what happens during the conquer phase.

  2. quick sort is another example of a divide and conquer algorithm. Explain what happens during the partitioning phase of the algorithm and why the choice of a pivot is important for efficiency.

  3. What does it mean for a sorting algorithm to be stable?

    • When would this characteristic useful?

    • For merge sort and quick sort, explain whether or not the algorithm is considered stable.

  4. For merge sort and quick sort, identify the best, average, and worst case complexities of each algorithm in terms of Big O.

    • Considering these complexities, why do most real-world sorting (ie. C++ Sort) implementations use some form of quick sort.

Submission

To submit your solution, you must initiate a Merge Request in your private assignments repository and assign it to the appropriate TA from the Reading 04 - TA assignment list.

Development Branch

To facility the Merge Request workflow, you must do your development in its own branch:

$ cd path/to/repo                 # Go to your repository
$ git checkout master             # Make sure we are on master branch first
$ git pull                        # Make sure we have changes from GitLab
$ git checkout -b reading04       # Create reading04 branch
...                               # Do your work
$ git commit                      # Commit your work (can do this multiple times)
$ git push -u origin reading04    # Push branch to GitLab