Sorting

Quick Sort

A high-performance divide-and-conquer sorting algorithm based on partitioning around a pivot.

What is Quick Sort?

Quick Sort is an efficient divide-and-conquer sorting algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Key Characteristics:

  • Divide-and-conquer strategy.
  • Unstable sort in its typical in-place formulation.
  • High cache efficiency and fast in practice.
  • Worst-case occurs with poor pivot choices.

Complexity Analysis

Avg Time Complexity: O(N * log N) average case
Space Complexity: O(log N) stack memory
Best Case: O(N * log N)
Worst Case: O(N^2) (reverse sorted array with end pivot)

How it Works Step-by-Step

  1. Select Pivot: Select a pivot element (e.g. last element, middle element, or random).
  2. Partitioning: Place elements smaller than pivot to its left, larger elements to its right. Place pivot at its final sorted position.
  3. Recurse Left: Invoke Quick Sort on the left partition (index low to pivot-1).
  4. Recurse Right: Invoke Quick Sort on the right partition (index pivot+1 to high).

Code Implementation

Worked Trace Example

Sorting [8, 3, 2, 7] using last element 7 as pivot:
1. Partitioning: elements < 7 go left, elements > 7 go right.
2. 3 and 2 are < 7, 8 is > 7.
3. Swap pivot 7 to index 2: [3, 2, 7, 8]. Pivot 7 is now in place.
4. Recurse on left [3, 2] with pivot 2: partitions to [2, 3].
5. Recurse on right [8] (single element: base case).
Result: Sorted array [2, 3, 7, 8].

Ready to Understand Quick Sort Visually?

Don't just read about it. Launch our interactive, premium algorithm visualizer to step through calculations in real-time.

Launch Quick Sort Visualizer →