aapl/mergesort.h

   1 /*
   2  *  Copyright 2001, 2002 Adrian Thurston <thurston@cs.queensu.ca>
   3  */
   4
   5 /*  This file is part of Aapl.
   6  *
   7  *  Aapl is free software; you can redistribute it and/or modify it under the
   8  *  terms of the GNU Lesser General Public License as published by the Free
   9  *  Software Foundation; either version 2.1 of the License, or (at your option)
  10  *  any later version.
  11  *
  12  *  Aapl is distributed in the hope that it will be useful, but WITHOUT ANY
  13  *  WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  14  *  FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for
  15  *  more details.
  16  *
  17  *  You should have received a copy of the GNU Lesser General Public License
  18  *  along with Aapl; if not, write to the Free Software Foundation, Inc., 59
  19  *  Temple Place, Suite 330, Boston, MA 02111-1307 USA
  20  */
  21
  22 #ifndef _AAPL_MERGESORT_H
  23 #define _AAPL_MERGESORT_H
  24
  25 #include "bubblesort.h"
  26
  27 #ifdef AAPL_NAMESPACE
  28 namespace Aapl {
  29 #endif
  30
  31 /**
  32  * \addtogroup sort
  33  * @{
  34  */
  35
  36 /**
  37  * \class MergeSort
  38  * \brief Merge sort an array of data.
  39  *
  40  * MergeSort can be used to sort any array of objects of type T provided a
  41  * compare class is given. MergeSort is not in-place, it requires temporary
  42  * storage equal to the size of the array. The temporary storage is allocated
  43  * on the heap.
  44  *
  45  * Objects are not made aware that they are being moved around in memory.
  46  * Assignment operators, constructors and destructors are never invoked by the
  47  * sort.
  48  *
  49  * MergeSort runs in worst case O(n*log(n)) time. In most cases it is slower
  50  * than QuickSort because more copying is neccessary. But on the other hand,
  51  * it is a stable sort, meaning that objects with the same key have their
  52  * relative ordering preserved. Also, its worst case is better. MergeSort
  53  * switches to a BubbleSort when the size of the array being sorted is small.
  54  * This happens when directly sorting a small array or when MergeSort calls
  55  * itself recursively on a small portion of a larger array.
  56  */
  57
  58 /*@}*/
  59
  60
  61 /* MergeSort. */
  62 template <class T, class Compare> class MergeSort
  63                 : public BubbleSort<T, Compare>
  64 {
  65 public:
  66         /* Sorting interface routine. */
  67         void sort(T *data, long len);
  68
  69 private:
  70         /* Recursive worker. */
  71         void doSort(T *tmpStor, T *data, long len);
  72 };
  73
  74 #define _MS_BUBBLE_THRESH 16
  75
  76 /* Recursive mergesort worker. Split data, make recursive calls, merge
  77  * results. */
  78 template< class T, class Compare> void MergeSort<T,Compare>::
  79                 doSort(T *tmpStor, T *data, long len)
  80 {
  81         if ( len <= 1 )
  82                 return;
  83
  84         if ( len <= _MS_BUBBLE_THRESH ) {
  85                 BubbleSort<T, Compare>::sort( data, len );
  86                 return;
  87         }
  88
  89         long mid = len / 2;
  90
  91         doSort( tmpStor, data, mid );
  92         doSort( tmpStor + mid, data + mid, len - mid );
  93
  94         /* Merge the data. */
  95         T *endLower = data + mid, *lower = data;
  96         T *endUpper = data + len, *upper = data + mid;
  97         T *dest = tmpStor;
  98         while ( true ) {
  99                 if ( lower == endLower ) {
 100                         /* Possibly upper left. */
 101                         if ( upper != endUpper )
 102                                 memcpy( dest, upper, (endUpper - upper) * sizeof(T) );
 103                         break;
 104                 }
 105                 else if ( upper == endUpper ) {
 106                         /* Only lower left. */
 107                         if ( lower != endLower )
 108                                 memcpy( dest, lower, (endLower - lower) * sizeof(T) );
 109                         break;
 110                 }
 111                 else {
 112                         /* Both upper and lower left. */
 113                         if ( compare(*lower, *upper) <= 0 )
 114                                 memcpy( dest++, lower++, sizeof(T) );
 115                         else
 116                                 memcpy( dest++, upper++, sizeof(T) );
 117                 }
 118         }
 119
 120         /* Copy back from the tmpStor array. */
 121         memcpy( data, tmpStor, sizeof( T ) * len );
 122 }
 123
 124 /**
 125  * \brief Merge sort an array of data.
 126  */
 127 template< class T, class Compare>
 128         void MergeSort<T,Compare>::sort(T *data, long len)
 129 {
 130         /* Allocate the tmp space needed by merge sort, sort and free. */
 131         T *tmpStor = (T*) new char[sizeof(T) * len];
 132         doSort( tmpStor, data, len );
 133         delete[] (char*) tmpStor;
 134 }
 135
 136 #ifdef AAPL_NAMESPACE
 137 }
 138 #endif
 139
 140 #endif /* _AAPL_MERGESORT_H */