merge_sort.h

Go to the documentation of this file.

/* Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; version 2 of the License.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301  USA
*/

#ifndef MERGE_SORT_INCLUDED
#define MERGE_SORT_INCLUDED

#include "sql_select.h"
#include <queue>

template<typename Element_type, typename Comp_func>
void insert_sort(Element_type **first, Element_type **last, Comp_func comp)
{
  for (Element_type **high_water_mark= first+1;
       high_water_mark < last;
       high_water_mark++)
  {
    for (Element_type **cur= high_water_mark; cur > first ; cur--)
    {
      if (comp(*(cur-1), *cur))
        break;

      Element_type *tmp= *(cur-1);
      *(cur-1)= *cur;
      *cur= tmp;
    }
  }
}


template<typename Element_type, typename Comp_func>
void merge_sort(Element_type **first, Element_type **last, Comp_func comp)
{
  const uint elements= last - first;

  /*
    Tests showed that the value 5 was a good number for JOIN_TAB
    ordering, which is the primary use case for this function
  */
  if (elements < 5)
  {
    insert_sort(first, last, comp);
    return;
  }
  Element_type **middle= first + (elements)/2;

  merge_sort (first, middle, comp);
  merge_sort (middle, last, comp);

  std::queue<Element_type *> merged;

  Element_type **cur1= first;
  Element_type **cur2= middle;

  for (uint i= 0; i < elements; i++)
  {
    DBUG_ASSERT (cur1 < middle || cur2 < last);

    if (cur1 == middle)
      merged.push(*cur2++);
    else if (cur2 == last)
      merged.push(*cur1++);
    else if (comp(*cur1, *cur2))
      merged.push(*cur1++);
    else
      merged.push(*cur2++);
  }

  Element_type **result= first;
  while (!merged.empty())
  {
    *result++= merged.front();
    merged.pop();
  }
}

#endif /* MERGE_SORT_INCLUDED */