Quick Sort

    DSA · Intermediate

    Definition

    Quick sort picks a pivot, partitions smaller elements left and larger right, then sorts each side recursively.

    Fastest in practice for in-memory arrays thanks to cache efficiency.

    Diagram

    [3 6 1 8 2] pivot 3[1 2] 3 [6 8][1 2 3 6 8]

    Flowchart

    Pick a pivotPartition around pivotRecurse left partRecurse right part

    Example: Quick sort

    def qs(a):
    if len(a) <= 1:
        return a
    p = a[0]
    return qs([x for x in a[1:] if x < p]) + [p] + qs([x for x in a[1:] if x >= p])
print(qs([3, 6, 1, 8, 2]))

    Output: [1, 2, 3, 6, 8]

    Complexity

    Average O(n log n) · Worst O(n²) · Space O(log n)

    Key points

    • Random pivot avoids worst case
    • Not stable
    • Quickselect finds k-th element in O(n) average

    Interview questions

    When is quick sort O(n²)?

    When the pivot is always the smallest or largest, e.g. sorted input with first-element pivot.

    More DSA topics

    ArraysLinked ListStackQueue