Quicksort implementation in C++

Question

I was wondering if this implementation of quicksort could be improved. Are there any things that I have done wrong?

template<typename Element>
size_t partition_quickSort(Element arr[], size_t start, size_t end) {
    auto pivot = arr[end];
    size_t index_partition = start;

    for (size_t i = start; i < end; ++i) {
        if (arr[i] <= pivot) {
            std::swap(arr[index_partition++], arr[i]);
        }
    }

    std::swap(arr[index_partition], arr[end]);
    return index_partition;
}

template<typename Element>
void quick_sort(Element arr[], size_t start, size_t end) {
    if (start < end) {
        size_t partition = partition_quickSort(arr, start, end);
        quick_sort(arr, start, partition - 1);
        quick_sort(arr, partition + 1, end);
    }
}
template<typename Element>
void quick_sort(Element arr[], size_t size) {
    quick_sort(arr, 0, size - 1);
}

Answer 1

1. There is just one thing wrong with your code.
   Don't ever call std::swap using a qualified name. Doing so cuts out user-defined functions which might be better, or actually viable. Use using std::swap; swap(*pa, *pb); or maybe std::iter_swap(pa, pb);.

2. Next, there's on thing sub-optimal. You are passing the range, as well as start and end. Knowing where in the overall range the part you are currently processing is does not help, so you can eliminate an argument.

3. Work on genericity by following C++ conventions.
   Useing half-open iterator-ranges allows wider application, you only need mutable forward-iterators.

4. Finally, Don't use <= for comparing the elements. All the standard algorithms only use <, and there's no compelling reason to break with that convention.

template <class ForwardIter>
void quicksort(const ForwardIter begin, const ForwardIter end) {
    if (begin == end) return;
    auto cur = begin;
    if (++cur == end) return;
    auto mid = begin;
    for (; cur != end; ++cur)
        if (*cur < *begin)
            std::iter_swap(cur, ++mid);
    std::iter_swap(begin, mid);
    quicksort(begin, mid);
    quicksort(++mid, end);
}

Answer 2

To add to @Deduplicator suggestions, I would recommend you improve your runtime. I mean there is nothing wrong in the implementation itself but currently you are using the last element of the array as pivot - this element can be the maximum or the minimum on each iteration making the complexity of this implementation in the worst case \$O(n^2)\$.

However if you take the median as pivot in quicksort you are bound to do the job with the least operations as possible (at least asymptotically \$O(n\log n)\$). Be aware that in order to get to this you need an algorithm that finds a median in complexity of \$O(n)\$.

There are quite a lot of information sources on the subject.

You should take a look here.