Divide and Conquer

Quick sort uses a divide-and-conquer strategy: break the problem into smaller subproblems, solve them, then combine the solutions.

The Process

1. Divide: Pick pivot and partition array
2. Conquer: Recursively sort sub-arrays
3. Combine: Nothing needed (already in place)

Visual Representation

Interactive Diagram

This interactive diagram requires JavaScript to be enabled.

Steps:

1. Pick pivot (3) and partition array
2. Left sub-array: elements less than pivot
3. Right sub-array: elements greater than pivot

Recursive Structure

The algorithm recursively partitions until it reaches the base case (0 or 1 element), which is already sorted.

Base Case

When the sub-array has 0 or 1 element, it’s already sorted. This is our stopping condition.

What’s Next?

Now that you understand how we divide, let’s learn the partition operation in detail.