Quicksort and Divide-and-Conquer

Question 1

What is the divide-and-conquer strategy?

Answer 1

Divide the problem into subproblems, solve them recursively, and combine their results.

Question 2

How does Quicksort work?

Answer 2

Chooses a pivot, partitions the array into elements less than and greater than the pivot, and recursively sorts them.

Question 3

What are the time complexities of Quicksort?

Answer 3

Best/average case: O(n log n), worst case: O(n²).
In-place, but not stable.

Question 4

When does Quicksort perform poorly?

Answer 4

When the pivot is consistently the smallest or largest element—e.g., sorted input with poor pivot choice.

Question 5

What is tail recursion and how is it relevant to Quicksort?

Answer 5

Tail recursion occurs when the recursive call is the last operation in a function—used in Quicksort optimizations.