*******************************************
Module 3: Sorting (Elemental, Merge, Quick)
*******************************************

.. note::

  This page only contains the notes for the module. It provides a big picture
  on the sorting algorithms.

+ Visualizations

  Due to the complexity of the sorting algorithms. Visualizations may greatly
  enhance the learning process. Below are two useful websites providing
  visualizations of common algorithms and data structures.

  * `visualgo.net <https://visualgo.net/en/sorting>`_
  * `Data Structure Visualization <https://www.cs.usfca.edu/~galles/visualization/Algorithms.html>`_

+ Categories

  * Comparison based

    - Best algorithm complexity :math:`\Theta(n \log n)`
    - The base type must be comparable (can use >, <, ==, etc.)
    - **selection**
    - **insertion**
    - bubble
    - shell
    - **quick**
    - **merge**
    - heap - to be covered in the next module

  * Other (special requirements on the data type)

    - Bucket
    - Radix
    - Counting

+ Complexity

  * simple :math:`\Theta(n^2)`: insert, selection, bubble
  * fast :math:`\Theta(n \log n)`: quick, merge, heap
  * linear

    - radix :math:`\Theta(nk) = \Theta(n)`
    - bucket :math:`\Theta(n + k) = \Theta(n)`

+ Storage Space

  * in-place

    - iterative sorting algorithms :math:`\Theta(1)`
    - recursive sorting algorithms :math:`\Theta(\log n)` to :math:`\Theta(n)`
      (due to the recursion stack)

  * not-in-place (out-of-place)

    - Merge sort :math:`\Theta(n)`

Comparison based sorting algorithms
===================================
+ In-place swap based sorting algorithms

  * Selection sort
  * Insertion sort
  * Bubble sort
  * Shell sort

+ Divide and conquer sorting algorithms

  * Merge sort
  * Quick sort

+ Hybrid sorting algorithms

  * Divide and conquer to reduce the problem size
  * in-place swap based sorting algorithms to sort when the problem size is
    small