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

*  Mergesort runs in :math:`O(N\log N)` worst-case running time.
*  It is a **divide-and-conquer** recursive algorithm.
*  The number of comparisons is nearly optimal.

Divide-And-Conquer
==================

*  Divide-And-Conquer is very important strategy in computer science.
*  It is able to solve large problem in :math:`O(N \log N)`.
*  The idea is simple:

   *  Breaking the problem into smaller sub-problems
   *  Solving the sub-problems
   *  Combine the sub-problem that are solved

Mergesort
=========

*  In the case of Mergesort the divide-and-conquer strategy is straight-forward.
*  We take our array that we need to sort.
*  We split the array recursively in two until each array contains only one element.
*  Then, merge the arrays by sorting them.

.. admonition:: Example
   :class: example

   *  Following is an example for the array :code:`[1,26,24,13,2,38,27,15]`.

   .. figure:: ./img/divide-merge.png
      :align: center


The Algorithm
=============

*  The algorithm is simple.
*  The merge function is based on the fact that each list are sorted before being merged.
*  Below the code for mergesort.

.. literalinclude:: ./MergeSort.java
   :language: java
   :linenos:
   :lines: 3-67