Optimizing quicksort

Question

I created simple quicksort algorithm using iterators. I'm happy with implementation but not with its speed. Profiler tells me that the slowest operation here is std::iter_swap. I don't really know how to improve this code. Note that I am not asking for different kind of quicksort algorithm but about improving this one.

#include <iterator>
#include <utility>
#include <functional>
template <typename RandomIt, typename Compare = std::less_equal<>>
void Sort::QuickSort(RandomIt first, RandomIt last, Compare compare = Compare())
{
 if (std::distance(first, last) <= 1) return;
 RandomIt pivot = Partition(first, last, compare);
 QuickSort(first, pivot, compare);
 QuickSort(std::next(pivot, 1), last, compare);
}
template <typename RandomIt, typename Compare>
RandomIt Sort::Partition(RandomIt first, RandomIt last, Compare compare)
{
 RandomIt pivot = MedianOf3(first, last, compare);
 RandomIt i = first;
 for (RandomIt j = first; j != pivot; ++j)
 if (compare(*j, *pivot)) {
 std::iter_swap(i, j);
 ++i;
 }
 std::iter_swap(i, pivot);
 return i;
}
template <typename RandomIt, typename Compare>
RandomIt Sort::MedianOf3(RandomIt first, RandomIt last, Compare compare)
{
 auto collectionSize = std::distance(first, last);
 RandomIt middle = std::next(first, collectionSize / 2);
 RandomIt targetPivot = std::prev(last, 1);
 if (compare(*middle, *first))
 std::iter_swap(middle, first);
 if (compare(*targetPivot, *first))
 std::iter_swap(targetPivot, first);
 if (compare(*middle, *targetPivot))
 std::iter_swap(middle, targetPivot);
 return targetPivot;
}

For testing I used vectors of 100 000 random elements. This code average sorting time is about 1626 ms on my machine and std::sort on the same set of data performs 10 times better, around 163 ms. I know that std::sort uses introsort but still quicksort shouldn't be 10 times slower.

• Toby Speight: You might get better reviews if you show the test program (if you don't want that part reviewed, just say so) and the necessary headers (at least <iterator>; perhaps others?).
• Toby Speight: I'd say that your performance problem is that std::iter_swap() is called too many times. Try moving i forwards from first while *i is less than *pivot and j backwards from last while *pivot is less than *j, then, when *j < *pivot < *i, perform the swap. Repeat until i==j.
• Ava: I'll try it, it will definitely improve performance. I will need some time for it, iterators have some edge cases in Hoare's scheme that I need to think about. Another minor question, is it ok to write something like std::prev(last, 1) or last - 1 is better?
• Toby Speight: Personally, I find last - 1 easier to read and should be defined for all RandomIterator types. I only use std::prev() when I really need a function to pass around. There could be something I missed, so don't just accept my say-so on that!

Answer 1

To get this code to compile I had to add the Sort namespace definition:

namespace Sort
{
 template <typename RandomIt, typename Compare = std::less_equal<>>
 void QuickSort(RandomIt first, RandomIt last, Compare compare = Compare());
 template <typename RandomIt, typename Compare>
 RandomIt Partition(RandomIt first, RandomIt last, Compare compare);
 template <typename RandomIt, typename Compare>
 RandomIt MedianOf3(RandomIt first, RandomIt last, Compare compare);
}

And I had to remove the default argument from the redeclaration of Sort::QuickSort:

template <typename RandomIt, typename Compare = std::less_equal<>>
void Sort::QuickSort(RandomIt first, RandomIt last, Compare compare)

Review requests should have issues like that already accounted for.

---

The performance of the Partition() function can be improved by doing fewer swaps. The current loop swaps when *j < *pivot, without considering whether *i is less or greater than *pivot. Instead, we can use two iterators, and advance them towards each other, swapping only when the ascending iterator points to an item greater than pivot and the descending iterator points to one smaller than pivot. The tricky bit is to avoid the iterators passing each other without terminating.