*********
Mergesort
*********

Overview
========
Mergesort is a classic example of a divide-and-conquer algorithm invented by
John von Neumann in 1945. Mergesort works by recursively dividing the unsorted
list into halves until each sub-list consists of a single element (and is
therefore considered sorted).It then merges these smaller lists in a way that
they remain sorted, eventually producing a single sorted list.

Characteristics
---------------
+ Divide and conquer algorithm
+ Comparison based (general purpose)
+ Recursive or iterative
+ Out-of-place

  * Requires additional memory
  * Efficient for linked lists

+ Efficient for large data sets
+ Stable - relative order of equal elements is preserved
+ Parallelizable

Algorithm Details
=================
+ Steps (top-down)

  #. Divide: Divide the n-element sequence to be sorted into two subsequences
     of ``n/2`` elements each.
  #. Conquer: Sort the two subsequences recursively using merge sort.
  #. Combine: Merge the two sorted subsequences to produce the sorted sequence.

+ Variations

   * top-down

    - usually recursive
    - stop repetition when the size of section is 1 or 0

  * bottom-up (iterative, not mentioned in the book)

    - usually iterative
    - merge all ``n`` size ``1`` sections (single element) into ``n/2`` size
      ``2`` sections
    - merge all size ``2`` lists to ``n/4`` size ``4`` lists
    - continue until done

Complexity
==========
+ Time

  * :math:`\Theta(n \log n)` best/worst/average case

+ Space

  * :math:`\Theta(n)` for new array
  * :math:`\Theta(\log n)` for recursion stack
  * Unoptimized recursive :math:`\Theta(n \log n)`
  * Optimized recursive :math:`\Theta(n)`
  * Iterative :math:`\Theta(n)`

Visualization Website
=====================
All available visualizations are for top-down merge sort.

+ https://www.toptal.com/developers/sorting-algorithms/merge-sort
+ http://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
+ https://visualgo.net/en/sorting