cxxsort.h 1.52 KB
Newer Older
Volker Springel's avatar
Volker Springel committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/*******************************************************************************
 * \copyright   This file is part of the GADGET4 N-body/SPH code developed
 * \copyright   by Volker Springel. Copyright (C) 2014-2020 by Volker Springel
 * \copyright   (vspringel@mpa-garching.mpg.de) and all contributing authors.
 *******************************************************************************/

/*! \file  cxxsort.h
 *  \brief various sort routines
 */

#ifndef GADGET4_CXXSORT_H
#define GADGET4_CXXSORT_H

#include <algorithm>

#include "../data/allvars.h"
#include "../data/mymalloc.h"
#include "../logs/logs.h"

template <typename T, typename Tcomp>
void mycxxsort_internal_serial(T *begin, T *end, T *buf, bool res_into_buf, Tcomp comp)
{
  std::size_t n = end - begin;
  if(n <= 1)
    {
      if((n == 1) && res_into_buf)
        *buf = *begin;
      return;
    }

  mycxxsort_internal_serial(begin, begin + n / 2, buf, !res_into_buf, comp);
  mycxxsort_internal_serial(begin + n / 2, end, buf + n / 2, !res_into_buf, comp);

  res_into_buf ? std::merge(begin, begin + n / 2, begin + n / 2, begin + n, buf, comp)
               : std::merge(buf, buf + n / 2, buf + n / 2, buf + n, begin, comp);
}

template <typename T, typename Tcomp>
double mycxxsort(T *begin, T *end, Tcomp comp)
{
  if(end - begin <= 1)
    return 0.;

  double t0 = Logs.second();

  T *buf = (T *)Mem.mymalloc("buf", (end - begin) * sizeof(T));

  mycxxsort_internal_serial(begin, end, buf, false, comp);

  Mem.myfree(buf);

  return Logs.timediff(t0, Logs.second());
}

#endif