Topic 15 - Mergesort

• Mergesort runs in \(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 \(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.

Example

• Following is an example for the array [1,26,24,13,2,38,27,15].

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.

/**
* 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 ];
}