Quad-sort: 4 sorting methods in one C++ file

I am fairly new to C++, and to have a break from all that Java programming, I decided to do something in C++, which is sorting. The four sorting algorithms are:

• Bubble Sort

• Insertion Sort

• Quick Sort

• Merge Sort

Code:

```
#include
#include
#include
#include
#include

#define SIZE 100
#define MAX 1000

typedef std::chrono::high_resolution_clock Clock;

void bubbleSort(int toSort[], int length);
void insertionSort(int toSort[], int length);
void quickSort(int toSort[], int length);
void mergeSort(int toSort[], int length);

void printArray(int arr[], int length)
{
for (int i = 0; i (end - start).count() (end - start).count() (end - start).count() (end - start).count() 0; j--) {
if (toSort[j] pivot);
if (beginPtr toSort[endPtr - 1]) {
swapElements(toSort, beginPtr, endPtr - 1);
}
return;
}
int splitIndex = partitionElements(toSort, beginPtr, endPtr);
quickSort(toSort, beginPtr, splitIndex );
quickSort(toSort, splitIndex, endPtr);
}

void quickSort(int toSort[], int length)
{
srand(time(NULL));
quickSort(toSort, 0, length);
}

void copyArray(int src[], int srcPos, int dest[], int destPos, int toCopyLength)
{
for (int i = 0; i < toCopyLength; i++) {
dest[i + destPos] = src[i + srcPos];
}
}

void mergeParts(int toSort[], int buffer[], int beginPtr, int middle,
int endPtr) {
copyArray(toSort, beginPtr, buffer, beginPtr, endPtr - beginPtr);

int index1 = beginPtr;
int index2 = middle;
int resultindex = beginPtr;

while (index1 < middle && index2 < endPtr) {
if (buffer[index1] < buffer[index2]) {
toSort[resultindex++] = buffer[index1++];
} else {
toSort[resultindex++] = buffer[index2++];
}
}

if (index1 < middle) {
copyArray(buffer, index1, toSort, resultindex, middle - index1);
}
if (index2 < endPtr) {
copyArray(buffer, index2, toSort, resultindex, endPtr -

This answer is mostly about design and good practice, and not so much about the algorithms themselves. Therefore, I will mostly use mergeSort in the examples.

For the sake of completeness: a sorting algorithm with an array + size interface is really C-ish. A proper C++ algorithm would take a pair of iterators and would be templated:

template
void mergeSort(RandomAccessIterator first, RandomAccessIterator last);

Moreover, most of the sorting algorithms in the standard library additionally accept an optional Compare parameter so that you can use something else than operator as a default:

template
>
void mergeSort(RandomAccessIterator first, RandomAccessIterator last,
               Compare compare={});

Now, let's have a look at the functions that you have reimplemented and that you can already find in the standard library (there is some overlap with other answers):

-
swapElements actually performs std::swap(toSort[i], toSort[j]);, or std::swap(it1, it2); if we consider that it1 and it2 are iterators corresponding to toSort + i and toSort + j. Note that we have templated mergeSort so that it can sort any random-access collection of any type. We would like our program to be able to use user-defined swap function instead of std::swap so that it can take advantage of the potential optimizations. We can use argument-dependent lookup to do the job:

using std::swap;
swap(*it1, *it2);

The first line tells the compiler to take std::swap into account for unqualified calls to swap. The second makes an unqualified call to swap: the compiler will check the types of it1 and it2 and search for a swap function in their associated namespace. If the lookup finds such a function, it will use it, otherwise it will use std::swap instead. Note that you can also use std::iter_swap which does exactly that:

std::iter_swap(it1, it2);

-
partitionElements could probably be replaced by std::partition.

-
You can replace copyArray by std::copy, or std::move if you know that you won't read the elements after they have been moved-from. Note that std::sort from the standard library is required to work with move-only types too, so it would be nice if you could ensure that your sorting algorithms work with such types (agreed, it's not trivial for quicksort).

-
I am pretty sure that mergeParts could be replaced by std::inplace_merge too.

So, taking all of that into account, here is how a modern C++ mergesort could look:

template
void mergeSort(RandomAccessIterator first, RandomAccessIterator last,
               Compare compare, std::size_t size) {
    if (size 
>
void mergeSortImpl(RandomAccessIterator first, RandomAccessIterator last,
               Compare compare={})
{
    std::size_t size = last - first;
    mergeSortImpl(first, last, compare, size);
}

This is better, but still not perfect: the algorithm currently works with random-access iterators, which is ok with std::vector, std::deque or std::array, but it also means that it doesn't work with std::list or std::forward_list which respectively expose bidirectional iterators and forward iterators. std::inplace_merge doesn't work with forward iterators (yet?) but it works fine with bidirectional iterators; here is what we have to change to make our mergeSort work with bidirectional iterators:

• Change iterators subtractions by calls to std::distance.

• Change the iterator-size addition by std::next.

• Change the name of the template parameters so that they do not lie.

Those simple functions from the header ` work with any category of iterator that is at least forward iterator. That also means that if one day std::inplace_merge works with forward iterators, then mergeSort will also work with forward iterators out-of-the-box and allow to sort, for example, singly linked lists. Here is our new enhanced algorithm:

template
void mergeSort(RandomAccessIterator first, RandomAccessIterator last,
               Compare compare, std::size_t size) {
    if (size 
>
void mergeSortImpl(RandomAccessIterator first, RandomAccessIterator last,
               Compare compare={})
{
    std::size_t size = std::distance(first, last);
    mergeSortImpl(first, last, compare, size);
}

More than an in-depth review of your algorithms, this answer was more about good pratices when writing algorithms. Basically, here is what you should keep in mind:

• Make your algorithms generic when possible.

• Iterators are the way to go (even though ranges will enhance things).

• The standard library can help you.

• Categories of iterators matter.

• Custom comparisons are cool (if you give std::greater<> instead of std::less<>` to a sorting algorithm, it will sort the collection in reverse order).

StackExchange Code Review Q#109341, answer score: 7