Back to Arrays & Sorting

Quick Sort

Pick a Pivot: Choose an element (e.g., the last element).
Partition: Reorder array so all elements smaller than pivot come before it, and all larger elements come after it.
Recursion: Recursively apply the above steps to the sub-array of smaller elements and sub-array of larger elements.

Quick Sort is a highly efficient, Divide-and-Conquer sorting algorithm. It selects a pivot element from the array and partitions the other elements into two sub-arrays according to whether they are less than or greater than the pivot.

         The Partitioning Mechanism:
        Pick a Pivot: Choose an element (e.g., the last element).

            Partition: Reorder array so all elements smaller than pivot come before
            it, and all larger elements come after it.
          
            Recursion: Recursively apply the above steps to the sub-array of
            smaller elements and sub-array of larger elements.

Python Implementation (Lomuto Partition)

def quick_sort(arr, low, high):
    if low < high:
        # pi is partitioning index, arr[pi] is now at right place
        pi = partition(arr, low, high)

        # Separately sort elements before partition and after partition
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

def partition(arr, low, high):
    pivot = arr[high]  # Pivot choice
    i = low - 1  # Index of smaller element

    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

Complexity Analysis

Best & Average Case Time: $O(n \log n)$ — Occurs when the pivot splits array evenly into two halves.
Worst Case Time: $O(n^2)$ — Occurs when the pivot is always the smallest or largest element (e.g., already sorted array with last element as pivot).
Space Complexity: $O(\log n)$ due to recursive call stack.
Stability: Unstable by default (swaps over long distances).