DSA — Quick Sort

What is Quick Sort?

Selects a pivot, partitions array around it, then recursively sorts partitions.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    return quick_sort(left) + middle + quick_sort(right)

In-Place Version

def quick_sort_inplace(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    
    if low < high:
        pivot_index = partition(arr, low, high)
        quick_sort_inplace(arr, low, pivot_index - 1)
        quick_sort_inplace(arr, pivot_index + 1, high)

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

Time Complexity

Case	Complexity
Best	O(n log n)
Average	O(n log n)
Worst	O(n²)

Characteristics

• Not stable
• In-place
• Fast in practice
• Cache friendly

Mini Practice

1. Implement quick sort
2. Choose different pivots
3. Use for finding kth element
4. Analyze worst case

Up Next

Continue with Heap Sort — heap-based sorting.