What is Quick Sort

Quick Sort is an efficient, comparison-based sorting algorithm that follows the divide-and-conquer approach. 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 recursively sorted.

How Does It Work

Consider this unsorted array:[10, 80, 30, 90, 40, 50, 70]

Partitioning Phase:

Choose last element as pivot (70)
Rearrange: elements < pivot on left, > pivot on right
→ [10, 30, 40, 50] [70] [80, 90]

Recursive Phase:

Apply same process to left sub-array [10, 30, 40, 50]
Apply same process to right sub-array [80, 90]
Combine results: [10, 30, 40, 50, 70, 80, 90]


  Original: 
  [10, 80, 30, 90, 40, 50, 70]
  
  First Partition (pivot=70):
  [10, 30, 40, 50][70][80, 90]
  
  Left Partition (pivot=50):
  [10, 30, 40][50]
  → already sorted
  
  Right Partition (pivot=90):
  [80][90]
  → already sorted
  
  Final:    
  [10, 30, 40, 50, 70, 80, 90]

Algorithm Steps

Choose Pivot:
- Select an element as pivot (commonly last/first/random element)
Partition:
- Reorder array so elements < pivot come before it
- Elements > pivot come after it
- Pivot is now in its final sorted position
Recurse:
- Apply quick sort to left sub-array (elements < pivot)
- Apply quick sort to right sub-array (elements > pivot)

Time Complexity

Best Case: O(n log n) (balanced partitions)
Average Case: O(n log n)
Worst Case: O(n²) (unbalanced partitions)

The log n factor comes from the division steps when partitions are balanced. The n² occurs when the pivot selection consistently creates unbalanced partitions.

Space Complexity

Quick Sort is O(log n) space complexity for the call stack in the average case, but can degrade to O(n) in the worst case with unbalanced partitions. It is generally considered an in-place algorithm as it doesn't require significant additional space.

Advantages

Fastest general-purpose in-memory sorting algorithm in practice
In-place algorithm (requires minimal additional memory)
Cache-efficient due to sequential memory access
Can be easily parallelized for better performance

Disadvantages

Not stable (relative order of equal elements may change)
Worst-case O(n²) performance (though rare with proper pivot selection)
Performance depends heavily on pivot selection strategy
Not ideal for linked lists (works best with arrays)

Pivot Selection Strategies

Last element: Simple but can lead to worst-case on sorted arrays
First element: Similar issues as last element
Random element: Reduces chance of worst-case scenarios
Median-of-three: Takes median of first, middle, last elements
Middle element: Often provides good balance

Quick Sort is the algorithm of choice for most standard library sorting implementations (like C's qsort, Java's Arrays.sort for primitives) due to its excellent average-case performance. It's particularly effective for large datasets that fit in memory.

Quick Sort Visualizer