quicksort

Quicksort is a divide-and-conquer sorting algorithm that orders a sequence by repeatedly partitioning it around a chosen element called the pivot. Tony Hoare developed it in 1959, and it remains one of the most widely used comparison sorts.

Each round picks a pivot and rearranges the surrounding elements so that every value smaller than the pivot sits before it and every larger value sits after it. This partition step fixes the pivot in its final position and splits the rest into two groups. Quicksort then sorts each group the same way, recursively, until every group holds one element or none and the full sequence is ordered.

Step through the visualizer below to watch one comparison at a time as each sub-array picks its pivot, sends every smaller value into a group on the left, drops the pivot between the two groups into its final position, and then repeats on each group:

The rearrangement happens within the original array, so quicksort sorts in place and needs only a small amount of extra memory for its recursive calls. Its speed depends on how evenly each pivot divides its range. Balanced splits give an average running time of O(n log n), while consistently lopsided splits, such as always choosing the smallest value in already-sorted data, slow it to O(n^2).

Real implementations lower that risk by choosing pivots with more care, often a random element or the median of the first, middle, and last values. Hybrid methods like introsort fall back to another sort once the recursion grows too deep, which caps the worst case at O(n log n). Quicksort is also unstable, meaning equal elements can finish in a different relative order than they started.

Related Resources

Tutorial

Thinking Recursively in Python

Learn how to work with recursion in your Python programs by mastering concepts such as recursive functions and recursive data structures.

intermediate python

For additional information on related topics, take a look at the following resources:

• Recursion in Python: An Introduction (Tutorial)
• Sorting Algorithms in Python (Tutorial)
• Introduction to Sorting Algorithms in Python (Course)
• Recursion in Python (Course)
• Thinking Recursively With Python (Course)
• Recursion in Python: An Introduction (Quiz)