Natural merge sort - follow-up

The previous iteration at Natural merge sort

Now my code relies on C++14 and looks like:

natural_merge_sort.h:

```
#ifndef NATURAL_MERGE_SORT_H
#define NATURAL_MERGE_SORT_H

#include
#include

/*****
Implements a simple, array-based queue of integers. All three operations run
in constant time. This queue, however, does not check for under-/overflow of
underlying buffer because of performance considerations.
*****/
class UnsafeIntQueue {
private:
const size_t MINIMUM_CAPACITY = 256;

size_t m_head;
size_t m_tail;
size_t m_size;
size_t m_mask;
size_t* m_buffer;

/*
Makes sure a capacity is at least 'MINIMUM_CAPACITY' and is a power of
two.
*/
size_t fixCapacity(size_t capacity)
{
capacity = std::max(capacity, MINIMUM_CAPACITY);
size_t s = 1;

while (s
std::unique_ptr build_run_size_queue(RandomIt first,
RandomIt lst,
Cmp cmp)
{
const size_t length = std::distance(first, lst);
UnsafeIntQueue* p_q = new UnsafeIntQueue(length / 2 + 1);

RandomIt head;
RandomIt left = first;
RandomIt right = left + 1;

const RandomIt last = lst - 1;

while (left enqueue(right - head);
std::reverse(head, right);
}
else
{
// Reading a ascending run.
while (left enqueue(left - head + 1);
}

++left;
++right;
}

if (left == last)
{
// Handle the case of an orphan element at the end of

There are still things you could improve to the implementation of the algorithm:

-
You are missing a #include for std::unique_ptr. It may be included by another standard library header, but it's not guaranteed. In fact, it triggered a compilation error with g++.

-
You could make natural_merge_sort take a default comparator such as std::less<> so that it can be called without an explicit comparator, like many of the standard library's algorithms:

template>
void natural_merge_sort(RandomIt first, RandomIt last, Cmp cmp=Cmp{})

-
Apparently, you failed to take into account @Hurkyl's comments in this follow-up. They are still worth it: don't manage memory manually if you don't have to. Using std::unique_ptr instead of size_t* is still an excellent idea:

std::unique_ptr m_buffer;

With such a member, you can totally get rid of UnsafeIntQueue's destructor and it will still make sure that the memory is always properly deallocated when an operation throws. Moreover, it will make your code follow the Rule of Zero which is more and more recommended by guidelines.

-
When I read RandomIt, I thought that your algorithm would work out-of-the-box for any random-access iterator type. Unfortunately, it does not, partly because of the following line:

RandomIt buffer = new value_type[length];

You should either make it clear in the documentation that your algorithm works only with pointers, or change your algorithm so that it works with any random-access iterator type. The latter requires significant work, so I won't propose any modification here.

-
When dealing with iterators, don't hesitate to use std::next and std::prev instead of writing +1 and -1. They make it obvious that the addition/subtraction is performed on an iterator and not on a size (while the meaning of +1 and -1 is not always obvious when reading an algorithm).

RandomIt head;
RandomIt left = first;
RandomIt right = std::next(left);

const RandomIt last = std::prev(lst);

Another benefit is that these functions accept bidirectional iterators. Changing the manual additions and subtractions by these functions sometimes make simple algorithms work with bidirectional iterators instead of just random-access iterators.

-
For the exact same reasons, using std::distance is good. Upon reading p_q->enqueue(right - head);, I actually had to look up the declarations of right and left to check whether they represented sizes or iterators. Using std::distance would have made it clear that they were iterators.

-
When you see things like 8 sizeof(t) in a function that performs bit tricks, it almost always means that 8 is a drop-in replacement for CHAR_BIT. That also means that what you actually want is std::numeric_limits::digits which is equivalent to CHAR_BIT sizeof(size_t) and helps to write generic code.

-
You can use constexpr to make it obvious that some constants are actually compile-time constants. Also, if a constant is part of the class and does not depend on the state of the class, make it static too:

static constexpr std::size_t MINIMUM_CAPACITY = 256;

Note that I also explicitly wrote a fully qualified std::size_t: some implementations of the standard library simply don't import the names from the standard C library in the global namespace, so prefixing every component of the standard library with std:: is good practice.

-
Instead of the traditional typedef inherited from C, don't hesitate to use the new shiny type alias offered by C++11. It looks more like a regular assignment (it makes it easier to reason about it) and can even be templated:

using value_type = typename std::iterator_traits::value_type;

StackExchange Code Review Q#86572, answer score: 6