quick sort

Quick sort, also written quicksort, is a divide-and-conquer sorting algorithm that orders a collection by partitioning it around a chosen pivot element. Values smaller than the pivot move before it and larger values after it, fixing the pivot in its final position and splitting the rest into two groups.

The same procedure then applies to each group through recursion, and the collection is fully ordered once every partition holds a single element. Because it rearranges elements within the collection itself, the algorithm sorts in place and typically needs only O(log n) extra space for its recursive calls.

The visualizer below steps through this partition-and-recurse process, showing how each pivot splits its sub-array into a smaller group and a larger one, settles into its final position, and then hands each group to the same procedure.

Its time complexity averages O(n log n), but degrades to O(n²) when the partitions stay unbalanced, such as when the pivot is always the first or last element and the input is already sorted. Pivot-selection strategies guard against this:

• Random pivot: Chooses an arbitrary element, which makes pathological inputs unlikely.
• Median-of-three: Uses the median of the first, middle, and last elements.

Tony Hoare developed quick sort in 1959, and its strong average performance has made it a common default in library sort routines. Most implementations aren’t stable, though, so equal elements can shift in relative order. Python’s built-in sorted() instead uses the stable Timsort algorithm.

Related Resources

Tutorial

Sorting Algorithms in Python

In this tutorial, you'll learn all about five different sorting algorithms in Python from both a theoretical and a practical standpoint. You'll also learn several related and important concepts, including Big O notation and recursion.

intermediate algorithms python

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

• Introduction to Sorting Algorithms in Python (Course)
• How to Use sorted() and .sort() in Python (Tutorial)
• Thinking Recursively in Python (Tutorial)
• Recursion in Python: An Introduction (Tutorial)
• Sorting Data With Python (Course)
• How to Use sorted() and .sort() in Python (Quiz)
• Thinking Recursively With Python (Course)
• Recursion in Python (Course)
• Recursion in Python: An Introduction (Quiz)