After I made that last post about my recursive bubble sort, a simple optimization occurred to me that would likely improve the speed of the algorithm.
template<typename T>
auto recursiveBubbleSort(T arr[], const int size, int pos=0, int count=0) -> void
{
if(size <= 1) return;
auto left {&arr[pos]};
auto right {&arr[++pos]};
if(*right < *left)
{
auto temp {*right};
*right = *left;
*left = temp;
}
if(&arr[pos] != &arr[size - 1 - count])
recursiveBubbleSort(arr, size, pos, count);
else if(count != (size - 2))
{
++count;
recursiveBubbleSort(arr, size, 0, count);
}
else
{
return;
}
}This actually makes it much closer to the iterative version, in that it takes into acount that the numbers at the end of the array are already sorted, and we needn't sort them again. Hard to believe I missed this detail! With the count variable comes in, the speed improves by about 2 times. Still not the best, or even close to std::sort(), but it's a fun exercise anyway.