Extensible sorting algorithm collection

Question

I have just learnt the strategy pattern. I'm using this pattern to implement this UML to better understand it. Here is the code snippet:

#include<iostream>
#include<functional>
#include<vector>
#include<memory>

template<class T>
class ISortingStrategy
{
public:
    virtual void sort(T *const org_ptr, std::size_t cnt, std::function<bool(const T&, const T&)> less_operator) = 0;
    virtual ~ISortingStrategy() = default;
};

template<class T>
class SelectSort final : public ISortingStrategy<T>
{
public:
    void sort(T *const org_ptr, std::size_t cnt, std::function<bool(const T&, const T&)> less_operator = std::less<T> ()) override
    {

        for(std::size_t i=0; i<cnt-1; i++)
        {
            T max = *(org_ptr+i);
            std::size_t max_idx = i;
            for(std::size_t j=i+1; j<cnt; j++)
            {
                if(less_operator(max, *(org_ptr+j)))
                {
                    max = *(org_ptr+j);
                    max_idx = j;
                }
            }

            if(max_idx !=i)
            {
                std::swap(*(org_ptr+i), *(org_ptr+max_idx));
            }
        }
    }

    ~SelectSort() override = default;
};

template<class T>
class MergeSort : public ISortingStrategy<T>
{
public:
    void sort(T *const org_ptr, std::size_t size, std::function<bool(const T&, const T&)> less_operator = std::less<T> ()) override
    {
        std::size_t max_sub_size = 2;
        while(max_sub_size<size)
        {
            if(size<=1)
            {
                return;
            }
            if(size==2)
            {
                if(less_operator(*org_ptr, *(org_ptr+1)))
                {
                    std::swap(*org_ptr, *(org_ptr+1));
                }
                return;
            }
            else
            {
                std::size_t size1{size>>1}, size2{size - size1};
                T* const ptr1 = org_ptr;
                T* const ptr2 = org_ptr+size1;

                sort(ptr1, size1, less_operator);
                sort(ptr2, size2, less_operator);

                auto res = merge(ptr1, size1, ptr2,  size2, less_operator);

                std::copy(res.begin(), res.end(), org_ptr);

                max_sub_size = res.size();
            }
        }
    }

    std::vector<T> merge(T * const ptr1, std::size_t size1, T* const ptr2, std::size_t size2, std::function<bool(const T&, const T&)> less_operator=std::less<T>())
    {
        std::size_t res_size = size1+size2;
        std::vector<T> res_ptr(size1+size2, T{});

        std::size_t part1_idx{0}, part2_idx{0};
        T part1_val{}, part2_val{};

        for(std::size_t k=0; k< res_size; k++)
        {
            if(part1_idx<size1)
            {
                part1_val = *(ptr1+part1_idx);
            }
            else
            {
                std::copy(ptr2+part2_idx, ptr2+size2, res_ptr.data()+k);
                break;
            }

            if(part2_idx<size2)
            {
                part2_val = *(ptr2+part2_idx);
            }
            else
            {
                std::copy(ptr1+part1_idx, ptr1+size1, res_ptr.data()+k);
                break;
            }

            if(less_operator(part1_val, part2_val))
            {
                ++part2_idx;
                res_ptr[k] = part2_val;
            }
            else
            {
                ++part1_idx;
                res_ptr[k] = part1_val;
            }
        }

        return res_ptr;
    }

    ~MergeSort() override = default;
};

template<class T>
class Client
{
public:
    Client(ISortingStrategy<T>* sort_ptr):m_sort_ptr(sort_ptr){};
    void sort(T *const org_ptr, std::size_t cnt, std::function<bool(const T&, const T&)> less_operator =  std::less<T> ())
    {
        m_sort_ptr->sort(org_ptr, cnt, less_operator);
    }
private:
    ISortingStrategy<T>* m_sort_ptr;
};

int main()
{
    Client<int> client(new MergeSort<int>());

    std::vector<int> vec{5, 9, 6, 11, 3, 7, 1};
    client.sort(const_cast<int*>(vec.data()), vec.size());

    for(const auto& val:vec)
    {
        std::cout << val << std::endl;
    }
}

Answer 1

This is a bad example

The class Client adds no value to the code whatsoever, in main() you can just call a strategy directly:

int main() {
    std::vector<int> vec{5, 9, 6, 11, 3, 7, 1};
    MergeSort<int>{}.sort(const_cast<int*>(vec.data()), vec.size());
    …
}

In fact, there is no reason to make anything a class at all, just making free functions merge_sort() and select_sort() is enough.

Also, while you use the strategy pattern for the sorting algorithm, you use std::function<> for the comparison function. If anything would benefit from the strategy pattern, it would be the comparison function, not the sorting algorithm!

Memory leak

Since you didn't use a smart pointer for m_sort_ptr, there will be a memory leak when client goes out of scope.

Use the same API as the standard library where possible

Your sort() functions don't look like std::sort(). In particular, you take a pointer to the first element and a size. The problem is that your code will then only work on data which is stored contiguously in memory, like in an array or in a std::vector, but it wouldn't be able to sort anything stored in a different type of container.

Ideally, your sort() functions look the same as std::sort() (or even better, like std::ranges::sort()). This makes it much more compatible with other container types, and it also makes it easier to switch between your sort() functions and the standard library's ones.

Minor issues

• Naming: Client is too generic.
• Unnecessary use of const_cast<>(); vec.data() already returns a non-const int*, and if it did return a const int*, then casting const away would probably not be a good idea anyway.
• Prefer to use '\n' instead of std::endl.
• Why is SelectSort final but MergeSort is not?

Answer 2

I haven't looked extensively, but a couple things immediately stand out to me.

Comparison operator

In your base class, the interface ISortingStrategy, you accept a parameter called less_operator. In all of your subclasses, you pass in std::less<T> as the default value for this parameter. But when I call sort on one of your subclasses, there is nothing stopping me from passing in some other comparison function, such as std::greater<T>. Wouldn't it then make more sense to just call this parameter operator (or better yet, something more clear like comparison_operator) since the user can choose any comparison function they want to use to sort their data?

Merge is different

Your MergeSort class implements the sort function from ISortingStrategy<T>, but it also has an additional merge function. This seems a little out of place, since merge has nothing to do with sort, so it doesn't really make sense that it's a part of the MergeSort class.