Partition and Quick Sort

Practice Exercise Intermediate Medium Choose / Explore / Unchoose Array Quick Sort

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement quick_sort(values). Return a new ascending list and do not call sorted or list.sort.

Starter code

def quick_sort(values):
    pass

Test cases

duplicates

{
  "args": [
    [
      4,
      1,
      4,
      2
    ]
  ]
}

Expected: [1,2,4,4]

reverse

{
  "args": [
    [
      5,
      3,
      1
    ]
  ]
}

Expected: [1,3,5]

Wizard outline

Step 1: Stop on a solved partition
Return an independent copy for zero or one value. The recursion must terminate on partitions that are already sorted.
Step 2: Partition around one pivot
Separate smaller, equal, and greater values. Three groups preserve duplicates and guarantee recursive groups exclude the pivot value.
Step 3: Sort every unresolved partition
Complete the divide-and-conquer recurrence. Every lower and higher value belongs on its side of every equal pivot, so independently sorted sides concatenate globally.

Footguns and prerequisites

Dropping values equal to the pivot loses duplicates.
Recursing on an unchanged partition can fail to terminate.
recursion and backtracking

Reviewed references

Python Compound Statements — Function Definitions

Recommended approach and implementation

Use a three-way pivot partition and recursively sort only strict lower and higher groups.

Why it works: Partitioning preserves every value and places all lower values before equals before higher values. Inductively sorted strict partitions therefore concatenate into a sorted permutation.

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)