Quick Sort

Quick Sort is a divide-and-conquer algorithm that picks a pivot element and partitions the array around it. It's one of the fastest sorting algorithms in practice, though worst-case performance is O(n²).

Quick Sort Visualization

Complexity

Time Complexity: O(n log n) average, O(n²) worst

Space Complexity: O(log n)

Pseudocode

function QuickSort(array, low, high):
  if low < high:
    pivot = Partition(array, low, high)
    QuickSort(array, low, pivot - 1)
    QuickSort(array, pivot + 1, high)
  
function Partition(array, low, high):
  pivot = array[high]
  i = low - 1
  
  for j from low to high-1:
    if array[j] < pivot:
      i++
      swap(array[i], array[j])
  
  swap(array[i+1], array[high])
  return i + 1

Related Algorithms

Merge Sort

Merge Sort is a divide-and-conquer algorithm that divides the array into halves, sorts them recursively, and then merges the sorted halves. It has consistent O(n log n) performance and is stable.

Time: O(n log n) | Space: O(n)