merge_sort.hpp File Reference

#include "array.hpp"
#include "hashmap.hpp"

Include dependency graph for merge_sort.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	less_eq_operator< T >

Functions
template<class T , class LEQ >
static void	merge_sort_sub (array< T > &a, int start, int end, array< T > &merge_buf)
template<class T , class LEQ >
void	merge_sort_leq (array< T > &a)
template<class T >
void	merge_sort (array< T > &a)
template<class T , class U , class LEQ >
static void	merge_sort_sub (array< T > &a, array< U > &b, int start, int end, array< T > &ma, array< U > &mb)
template<class T , class U , class LEQ >
void	merge_sort_leq (array< T > &a, array< U > &b)
template<class T , class LEQ >
array< int >	merge_sort_leq_permutation (array< T > &a)
template<class T >
array< int >	merge_sort_leq_permutation (array< T > &a)
template<class T >
array< T >	permute (array< T > &a, array< int > b)

Function Documentation

merge_sort_sub() [1/2]

template<class T , class LEQ >

static void merge_sort_sub ( array< T > & a, int start, int end, array< T > & merge_buf )

static

Definition at line 27 of file merge_sort.hpp.

                                                                      {
  if (end - start <= 1) return;
  if (end - start == 2) {
    if (!LEQ::leq (a[start], a[start + 1])) {
      merge_buf[start]= a[start];
      a[start]        = a[start + 1];
      a[start + 1]    = merge_buf[start];
    }
    return;
  }
  int middle= (start + end) >> 1;
  merge_sort_sub<T, LEQ> (a, start, middle, merge_buf);
  merge_sort_sub<T, LEQ> (a, middle, end, merge_buf);
  int i, j, k;
  for (i= start, j= middle, k= start; (i < middle) && (j < end);)
    if (LEQ::leq (a[i], a[j])) merge_buf[k++]= a[i++];
    else merge_buf[k++]= a[j++];
  j= k;
  while (i != middle)
    a[k++]= a[i++];
  for (i= start; i < j; i++)
    a[i]= merge_buf[i];
}

merge_sort_leq() [1/2]

template<class T , class LEQ >

void merge_sort_leq

(

array< T > &

a

)

Definition at line 53 of file merge_sort.hpp.

                             {
  array<T> merge_buf (N (a));
  merge_sort_sub<T, LEQ> (a, 0, N (a), merge_buf);
}

merge_sort()

template<class T >

void merge_sort ( array< T > & a )

inline

Definition at line 60 of file merge_sort.hpp.

                         {
  merge_sort_leq<T, less_eq_operator<T>> (a);
}

merge_sort_sub() [2/2]

template<class T , class U , class LEQ >

static void merge_sort_sub ( array< T > & a, array< U > & b, int start, int end, array< T > & ma, array< U > & mb )

static

Definition at line 70 of file merge_sort.hpp.

                              {
  if (end - start <= 1) return;
  if (end - start == 2) {
    if (!LEQ::leq (a[start], a[start + 1])) {
      ma[start]   = a[start];
      a[start]    = a[start + 1];
      a[start + 1]= ma[start];
      mb[start]   = b[start];
      b[start]    = b[start + 1];
      b[start + 1]= mb[start];
    }
    return;
  }
  int middle= (start + end) >> 1;
  merge_sort_sub<T, U, LEQ> (a, b, start, middle, ma, mb);
  merge_sort_sub<T, U, LEQ> (a, b, middle, end, ma, mb);
  int i, j, k;
  for (i= start, j= middle, k= start; (i < middle) && (j < end);)
    if (LEQ::leq (a[i], a[j])) {
      mb[k]  = b[i];
      ma[k++]= a[i++];
    }
    else {
      mb[k]  = b[j];
      ma[k++]= a[j++];
    }
  j= k;
  while (i != middle) {
    b[k]  = b[i];
    a[k++]= a[i++];
  }
  for (i= start; i < j; i++) {
    b[i]= mb[i];
    a[i]= ma[i];
  }
}

merge_sort_leq() [2/2]

template<class T , class U , class LEQ >

void merge_sort_leq	(	array< T > &	a,
		array< U > &	b )

Definition at line 110 of file merge_sort.hpp.

                                          {
  ASSERT (N (a) == N (b), "arrays of the same length expected");
  array<T> ma (N (a));
  array<U> mb (N (b));
  merge_sort_sub<T, U, LEQ> (a, b, 0, N (a), ma, mb);
}

merge_sort_leq_permutation() [1/2]

template<class T , class LEQ >

array< int > merge_sort_leq_permutation

(

array< T > &

a

)

Definition at line 119 of file merge_sort.hpp.

                                         {
  array<int> b (N (a));
  for (int i= 0; i < N (a); i++)
    b[i]= i;
  merge_sort_leq<T, int, LEQ> (a, b);
  return b;
}

merge_sort_leq_permutation() [2/2]

template<class T >

array< int > merge_sort_leq_permutation

(

array< T > &

a

)

Definition at line 129 of file merge_sort.hpp.

                                         {
  return merge_sort_leq_permutation<T, less_eq_operator<T>> (a);
}

permute()

template<class T >

array< T > permute	(	array< T > &	a,
		array< int >	b )

Definition at line 135 of file merge_sort.hpp.

                                    {
  ASSERT (N (a) == N (b), "arrays of the same length expected");
  array<T> r (N (a));
  for (int i= 0; i < N (a); i++)
    r[i]= a[b[i]];
  return r;
}