## Sorting for beginers — at compile time

Every serious programmer knows how to write some of simple cumbersome `O(n^2)`

sorting algorithms.
Do you know how to use templates in C++? Great!
Today I want to show you some advanced fun with C++ templating principles.
Or is it a routine to sort types by their `sizeof`

with merge sort by a compiler?

#### Why doing such nasty things?

This article is an interesting detail of my project called attr-MU which I have written some time ago. We start with some simple demonstration of C++ parameter pack. Then we move to simple Merge sort implementation. We left Bubble sort as an optional exercise for a reader.

#### Concat operation — example

C++ meta programming feels a little bit like logic programming in Prolog. It will helps you knowledge any non-procedural language.
Let `struct list<...>`

be a structure with variadic number of template parameters.
We define `Concat(list<a`

as _{1}, …, a_{n}>, list<b_{1}, …, b_{m}>)`list<a`

.
With some basic knowledge of specialization we can express it in the language of templates really simply:
_{1}, …, a_{n}, b_{1}, …, b_{m}>

```
template<typename... Ts> struct concat {};
template<typename... Ts, typename... TTs>
struct concat<list<Ts...>, list<TTs...>> {
using type = list<Ts..., TTs...>;
};
```

#### Shift operation — the first step

If we think about parameter pack as it would be a list, than how we can push new element front?
This is often called shift. We can think about shift as a special case of `Concat`

, therefore this is even simplier than previous example:

```
template<typename... Ts> struct shift {};
template<typename T, typename... TTs>
struct shift<T, list<TTs...>> {
using type = typename cat<list<T>, list<TTs...>>::type;
};
```

Notice the necessary occurance of the `typename`

keyword in the `using`

declaration.

#### Functional evergreen — drop & take

Let make it more complicated. You should know about integral template parameters before (its the first `int`

param in the following example).
If so, we want to forget all type parameter until the indexing variable is equal zero:

```
template<int I, typename List> struct drop { using type = list<>; };
template<int I, typename T, typename... Ts>
struct drop<I, list<T, Ts...>> {
using type = typename std::conditional<
(I > 0),
typename drop<I-1, list<Ts...>>::type,
list<T, Ts...>
>::type;
};
```

As you can see, the main trick is in separation of the first type param from others.
The way the code is indent suggests that there is a (terminating) condition.
For this purpouses is used `std::conditional`

from standard lib.
Notice we can get value of the `I-1`

as a compile-time constant.
Moreover, in the definition of `Take`

operation we use previously written `Shift`

:

```
template<int I, typename List> struct take { using type = list<>; };
template<int I, typename T, typename... Ts>
struct take<I, list<T, Ts...>> {
using type = typename std::conditional<
(I > 0),
shift_t<T, typename take<I-1, list<Ts...>>::type>,
list<>
>::type;
};
```

#### Lets merge …

Now it comes to scene the order. In our example we will sort by
the number of bytes of the object representation of type — `sizeof`

. Follows code of a specialization. It looks like as a normal Merge sort now, does't it?

```
template<typename T, typename... Ts, typename TT, typename... TTs>
struct merge<list<T, Ts...>, list<TT, TTs...>> {
using type = typename std::conditional<
(sizeof(T) > sizeof(TT)),
shift_t<T , typename merge<list< Ts...>, list<TT, TTs...>>::type>,
shift_t<TT, typename merge<list<T, Ts...>, list<TTs...>>::type>
>::type;
};
```

#### … and sort! Horray!

We have defined all the necessary tools for sorting. If you think over for a while how to use it, you should be able to write it on your own —

```
template<typename L> struct merge_sort { using type = L; };
template<typename T> struct merge_sort<list<T>> { using type = list<T>; };
template<typename T, typename... Ts>
struct merge_sort<list<T, Ts...>> {
using type = merge_t<
typename merge_sort< take_t< ((sizeof...(Ts)+1) / 2), list<T,Ts...>> >::type,
typename merge_sort< drop_t< ((sizeof...(Ts)+1) / 2), list<T,Ts...>> >::type
>;
};
```

In this preview we used another specialization to terminate first-order recursion;
list of one element is sorted by default. You may find out, that we use e.g. `take_t`

instead of `typename take<...>::type`

. This usage is taken from standard libraly and
it is created with `using take_t = typename take<...>::type;`

.

The complete compile time Merge sort together with Bubble sort is implemented in base.hpp, a main header of the attr-MU project. Feel free to discuss with you anything and thanks for your attention! Stay turned!