1. Choose a pivot element from the array
2. Partition: reorder elements so that:
- Elements less than pivot go to the left
- Elements greater than pivot go to the right
3. Recursively apply steps 1-2 to left and right sub-arrays
4. Base case: arrays with 0 or 1 element are already sorted
Time Complexity:
- Best Case: O(n log n) - balanced partitions
- Average Case: O(n log n) - random data
- Worst Case: O(n²) - already sorted or all equal
Space Complexity:
- O(log n) average - recursive call stack
- O(n) worst case - unbalanced partitions
Quick Sort is:
- Unstable (relative order of equal elements may change)
- In-place (only requires O(log n) extra space)
- Cache-friendly (good locality of reference)
// Basic Quick Sort
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[arr.length - 1];
const left = [];
const right = [];
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
// In-place Quick Sort (more efficient)
function quickSortInPlace(arr, low = 0, high = arr.length - 1) {
if (low < high) {
const pivotIndex = partition(arr, low, high);
quickSortInPlace(arr, low, pivotIndex - 1);
quickSortInPlace(arr, pivotIndex + 1, high);
}
return arr;
}
function partition(arr, low, high) {
const pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]]; // Swap
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}
# Basic Quick Sort
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[-1]
left = [x for x in arr[:-1] if x < pivot]
right = [x for x in arr[:-1] if x >= pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
# In-place Quick Sort
def quick_sort_in_place(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low < high:
pivot_index = partition(arr, low, high)
quick_sort_in_place(arr, low, pivot_index - 1)
quick_sort_in_place(arr, pivot_index + 1, high)
return arr
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap arr[i+1] and arr[high] (pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
}
#include <vector>
int partition(std::vector<int>& arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
# Last element (simple but poor for sorted data)
pivot = arr[high]
# First element
pivot = arr[low]
# Middle element (better for sorted data)
mid = (low + high) // 2
pivot = arr[mid]
# Median-of-three (good balance)
def median_of_three(arr, low, high):
mid = (low + high) // 2
if arr[low] > arr[mid]:
arr[low], arr[mid] = arr[mid], arr[low]
if arr[low] > arr[high]:
arr[low], arr[high] = arr[high], arr[low]
if arr[mid] > arr[high]:
arr[mid], arr[high] = arr[high], arr[mid]
return mid # Return median index
# Random pivot (prevents worst case on sorted data)
import random
pivot_index = random.randint(low, high)
arr[pivot_index], arr[high] = arr[high], arr[pivot_index]
pivot = arr[high]
# Handles duplicates efficiently - O(n) for arrays with many duplicates
def quick_sort_3way(arr, low, high):
if low >= high:
return
lt, gt = low, high
pivot = arr[low]
i = low + 1
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1
i += 1
elif arr[i] > pivot:
arr[gt], arr[i] = arr[i], arr[gt]
gt -= 1
else:
i += 1
quick_sort_3way(arr, low, lt - 1)
quick_sort_3way(arr, gt + 1, high)
# Avoids recursion stack overflow for large arrays
def quick_sort_iterative(arr):
stack = [(0, len(arr) - 1)]
while stack:
low, high = stack.pop()
if low < high:
pivot_index = partition(arr, low, high)
# Push sub-arrays to stack
stack.append((low, pivot_index - 1))
stack.append((pivot_index + 1, high))
return arr
Algorithm | Best | Average | Worst | Space | Stable
---------------|-----------|-----------|-----------|----------|--------
Quick Sort | O(n log n)| O(n log n)| O(n²) | O(log n) | No
Merge Sort | O(n log n)| O(n log n)| O(n log n)| O(n) | Yes
Heap Sort | O(n log n)| O(n log n)| O(n log n)| O(1) | No
Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes
When to use Quick Sort:
✓ Average case performance matters most
✓ Memory is limited (in-place sorting)
✓ Cache performance is important
✗ Stability is required (use Merge Sort)
✗ Guaranteed O(n log n) needed (use Heap/Merge Sort)