Quick Sort in Python
Learn Quick Sort in Python! A beginner-friendly guide to the famous Divide and Conquer algorithm. See how pivots and partitioning make sorting blazing fast.
Try it yourself
Run this code directly in your browser. Click "Open in full editor" to experiment further.
Click Run to see output
Or press Ctrl + Enter
How it works
Quick Sort is arguably the most famous sorting algorithm in the world! Like Merge Sort, it uses the incredibly smart Divide and Conquer strategy, but in a totally different and super memory-efficient way.
How It Works (The Pivot Strategy)
Imagine you have a messy line of kids sorted randomly by height.
1. Pick a Pivot: You just point to one random kid (let's say the last kid in line) and say, "You are the Pivot!"
2. Partitioning (The Magic Step): You tell everyone shorter than the Pivot to stand on their left, and everyone taller than the Pivot to stand on their right.
3. Boom! The Pivot kid is now standing in their exact, permanent, perfectly sorted spot in the final line! They never have to move again.
4. Recursion: Now you just repeat this exact same process for the messy subgroup on the left, and the messy subgroup on the right.
Time and Space Complexity
quick_sort_inplace version requires almost zero extra memory (O(log n) for the recursion stack)! Since we just swap kids around inside the original line without making new lines, it's incredibly memory-efficient compared to Merge Sort space-wise!Why is it so popular?
Because it does all the sorting in-place (right inside the original array), it's incredibly friendly to your computer's CPU cache. In the real world, the standard Quick Sort often runs significantly faster than Merge Sort!
Related examples
Merge Sort in Python
Learn Merge Sort in Python! A fun, beginner-friendly guide to the Divide and Conquer sorting strategy with guaranteed fast performance.
Bubble Sort in Python
Learn the Bubble Sort algorithm in Python! Step-by-step visual explanation with beginner-friendly, optimized Python code.
