********************
Topic 15 - 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

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

   .. figure:: ../img/topic15/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.

.. code-block:: cpp

   /**
   * Mergesort algorithm (driver).
   */
   template <typename Comparable>
   void mergeSort( vector<Comparable> & a )
   {
      vector<Comparable> tmpArray( a.size( ) );

      mergeSort( a, tmpArray, 0, a.size( ) - 1 );
   }

   /**
   * Internal method that makes recursive calls.
   * a is an array of Comparable items.
   * tmpArray is an array to place the merged result.
   * left is the left-most index of the subarray.
   * right is the right-most index of the subarray.
   */
   template <typename Comparable>
   void mergeSort( vector<Comparable> & a,
   vector<Comparable> & tmpArray, int left, int right )
   {
      if( left < right )
      {
         int center = ( left + right ) / 2;
         mergeSort( a, tmpArray, left, center );
         mergeSort( a, tmpArray, center + 1, right );
         merge( a, tmpArray, left, center + 1, right );
      }
   }

   /**
   * Internal method that merges two sorted halves of a subarray.
   * a is an array of Comparable items.
   * tmpArray is an array to place the merged result.
   * leftPos is the left-most index of the subarray.
   * rightPos is the index of the start of the second half.
   * rightEnd is the right-most index of the subarray.
   */
   template <typename Comparable>
   void merge( vector<Comparable> & a, vector<Comparable> & tmpArray,
   int leftPos, int rightPos, int rightEnd )
   {
      int leftEnd = rightPos - 1;
      int tmpPos = leftPos;
      int numElements = rightEnd - leftPos + 1;

      // Main loop
      while( leftPos <= leftEnd && rightPos <= rightEnd )
         if( a[ leftPos ] <= a[ rightPos ] )
            tmpArray[ tmpPos++ ] = a[ leftPos++ ];
         else
            tmpArray[ tmpPos++ ] = a[ rightPos++ ];

      while( leftPos <= leftEnd ) // Copy rest of first half
         tmpArray[ tmpPos++ ] = a[ leftPos++ ];

      while( rightPos <= rightEnd ) // Copy rest of right half
         tmpArray[ tmpPos++ ] = a[ rightPos++ ];

      // Copy tmpArray back
      for( int i = 0; i < numElements; ++i, --rightEnd )
         a[ rightEnd ] = tmpArray[ rightEnd ];
   }