Comparative study of Quicksort

Context

A hands-on assignment for Design and Analysis of Algorithms at PUC Minas, done as a team of three with Marcus and Gabriel. Starting from an exercise in Ziviani's algorithms textbook, the goal was to compare three versions of Quicksort in practice and check the numbers against the theory.

Problem

Asymptotic analysis counts comparisons and swaps. The question was whether that count still explains running time on a modern processor, and where the best point for switching from Quicksort to Insertion Sort on small subarrays actually lies.

Approach

The three versions were written in C++17 on top of a single parameterized engine, so that all of them counted comparisons and swaps in exactly the same way:

• Classic recursive, which partitions down to single-element subarrays;
• Hybrid, which stops partitioning below M elements and finishes with Insertion Sort;
• Hybrid with median-of-three, same as the previous one, with the pivot chosen among the first, middle, and last elements.

Each version ran on five test datasets (random, sorted, reverse-sorted, with many duplicates, and nearly sorted) at four sizes, from 1,000 to 500,000 elements, measuring time, comparisons, and swaps. Everything is reproducible with make tudo or with the Docker containers, which also generate the charts and compile the LaTeX report.

Results

• Cutoff point M = 40. The minimum number of comparisons is stable at M ≈ 20–25, but timing is noisy; using the criterion of the smallest M within 2% of the best time, the value came out above the 5 to 25 range from the classic literature. The explanation lies in modern hardware: cache and branch prediction favor Insertion Sort for longer.
• Hybrids 16% to 54% faster than the pure recursive version (median of 28%), never losing in any configuration.
• Worst case confirmed: with a sorted array and the pivot at the first element, the comparisons/n² ratio converged to exactly 0.5000, the n(n − 1)/2 comparisons predicted by theory. For n = 50,000, the gap relative to a good pivot reached ~2,000× in comparisons and ~1,200× in running time.

What stood out most

On random data, the hybrid version performs more comparisons and swaps than the recursive one and is still always faster. Operation counts remain correct for asymptotic analysis, but they no longer predict real running time: cache and branch prediction matter as much as the number of operations.

Median-of-three was also a surprise: with the same M, it only reduces comparisons on random data (2% to 9%) and is about 1% worse on sorted inputs. Its value lies in protecting against bad pivots, where the difference is three orders of magnitude.