Skip to content
Hello Python
Algorithm1 Practice4 Interview

Quick Sort

Partition around pivots and recursively sort partitions with average O(n log n) time. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Quick Sort when the prompt's constraints and required operations match this shape: Partition around pivots and recursively sort partitions with average O(n log n) time.

Pybit demonstrates Quick Sort in a professional Python interview workspace.
On this page · Partition Around a Pivot

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Quick Sort Code Labs

Partition Around a Pivot

Partitioning rearranges one range so values on one side satisfy the pivot relation and values on the other side do not. The pivot reaches a final position for that partition scheme.

Maintain Three Partition Regions

During Lomuto partition, the prefix is less than or equal to pivot, the middle has been inspected and is greater, and the suffix is unseen. Swapping an accepted value grows the first region.

Trace Lomuto Partition

Reference
def partition_trace(values):
    values=values.copy();pivot=values[-1];boundary=0;trace=[]
    for index in range(len(values)-1):
        if values[index]<=pivot:
            values[boundary],values[index]=values[index],values[boundary];trace.append(values.copy());boundary+=1
    values[boundary],values[-1]=values[-1],values[boundary];trace.append(values.copy());return trace
Practice

Implement partition_trace(values). Use the last value as pivot and return array states after each swap, including final pivot placement.

Public tests

  • Grow the less-or-equal region

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Recurse Only on Unsettled Sides

After pivot placement, exclude the pivot from both recursive ranges. Base cases of size zero or one prevent repeated boundaries and guarantee termination.

Quick Sort Values

Reference
def quick_sort(values):
    values=values.copy()
    def sort(left,right):
        if left>=right:return
        pivot=values[right];boundary=left
        for index in range(left,right):
            if values[index]<=pivot:values[boundary],values[index]=values[index],values[boundary];boundary+=1
        values[boundary],values[right]=values[right],values[boundary]
        sort(left,boundary-1);sort(boundary+1,right)
    sort(0,len(values)-1);return values
Practice

Implement quick_sort(values). Return a sorted copy using in-place partitioning on the copy.

Public tests

  • Sort both unsettled partitions

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Control Worst Case and Stack Depth

Balanced pivots give expected O(n log n); consistently extreme pivots give O(n squared) and O(n) recursion depth. Randomization or median heuristics reduce adversarial risk, and sorting the smaller side first can bound stack depth.

Explain It in an Interview

Say: “These regions are the partition invariant; each scan step classifies one value, then the pivot is final.” State duplicate policy, input mutation, average and worst-case time, and recursion-space behavior.

Python Version Note

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Quick Sort complete workflowO(n log n) average, O(n^2) worstO(n log n) average, O(n^2) worstUse a three-way pivot partition and recursively sort only strict lower and higher groups.

Space

O(n) for the focused Partition and Quick Sort implementation.

Assumptions

  • Partitioning preserves every value and places all lower values before equals before higher values. Inductively sorted strict partitions therefore concatenate into a sorted permutation.
  • The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

  1. State the precise Quick Sort invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. The resolved region satisfies the target ordering relation.
  3. The unresolved region still contains every item not yet placed.
  4. Partition values around one pivot. Preserve this claim after every transition.
  5. Recurse only on smaller partitions and combine all duplicates. Preserve this claim after every transition.

When To Use Or Avoid Quick Sort

Use It When

  • Use Quick Sort when this precondition is stated or can be proved: The comparison, key domain, stability need, and memory constraints match the selected ordering method.
  • Use it when this maintained state removes repeated work: The resolved region satisfies the target ordering relation.

Choose Another Tool When

  • Avoid Quick Sort when this precondition is absent: The comparison, key domain, stability need, and memory constraints match the selected ordering method.
  • Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: The comparison, key domain, stability need, and memory constraints match the selected ordering method.

Avoid

def quick_sort(values):
    pass

Use instead

def quick_sort(values):
    if len(values) < 2:
        return list(values)
    pivot = values[len(values) // 2]
    lower = [value for value in values if value < pivot]
    equal = [value for value in values if value == pivot]
    higher = [value for value in values if value > pivot]
    return quick_sort(lower) + equal + quick_sort(higher)

Where you will hit this: Partition and Quick Sort(opens in a new tab)

Breaking the state transition

Keeps only one pivot and drops duplicate pivot values.

Prevent it: Preserve this proof obligation: The resolved prefix, suffix, rank, digit pass, or bucket remains in its documented final relation.

Avoid

def quick_sort(values):
    if len(values)<2:return list(values)
    p=values[0]; return quick_sort([x for x in values[1:] if x<p])+[p]+quick_sort([x for x in values[1:] if x>p])

Use instead

def quick_sort(values):
    if len(values) < 2:
        return list(values)
    pivot = values[len(values) // 2]
    lower = [value for value in values if value < pivot]
    equal = [value for value in values if value == pivot]
    higher = [value for value in values if value > pivot]
    return quick_sort(lower) + equal + quick_sort(higher)

Where you will hit this: Partition and Quick Sort(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(n log n) average, O(n^2) worst.

Avoid

def quick_sort(values):
    if len(values)<2:return list(values)
    p=values[0]; return quick_sort([x for x in values[1:] if x<p])+[p]+quick_sort([x for x in values[1:] if x>p])

Use instead

def quick_sort(values):
    if len(values) < 2:
        return list(values)
    pivot = values[len(values) // 2]
    lower = [value for value in values if value < pivot]
    equal = [value for value in values if value == pivot]
    higher = [value for value in values if value > pivot]
    return quick_sort(lower) + equal + quick_sort(higher)

Where you will hit this: Car Fleet(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.