DSA interview question

Quick Sort

Medium · Algorithms · Topics: sorting, divide and conquer, recursion

The problem

A search engine re-ranks millions of results in memory for every query, and memory is tight, so an O(n)-extra-space merge sort is unwelcome. Quick sort sorts in place and is usually the fastest general-purpose comparison sort in practice. Pick a pivot, partition the array so smaller elements sit to its left and larger ones to its right (the pivot is now in its final position), then recursively sort both sides. The danger is a bad pivot: always choosing the first or last element makes sorted input degrade to O(n²). A random pivot makes that practically impossible.

Example: [4, 6, 2, 5, 7, 9, 1, 3] → [1, 2, 3, 4, 5, 6, 7, 9].

Function signature

void quickSort(vector<int>& a);  // sorts a in non-decreasing order, in place

Test cases

Input `a`	Output	Explanation
`[4, 6, 2, 5, 7, 9, 1, 3]`	`[1, 2, 3, 4, 5, 6, 7, 9]`
`[5, 2, 9, 1, 5, 6]`	`[1, 2, 5, 5, 6, 9]`	Duplicates
`[1, 2, 3, 4, 5]`	`[1, 2, 3, 4, 5]`	Sorted input: random pivot avoids O(n²)
`[5, 4, 3, 2, 1]`	`[1, 2, 3, 4, 5]`	Reverse sorted
`[3, 3, 3, 3]`	`[3, 3, 3, 3]`	All equal
`[42]`	`[42]`
`[]`	`[]`

(Confirm: in place, non-decreasing; stability isn't required; the code cross-checks 1,000 random arrays against std::sort.)

How interviewers phrase it

"Implement quick sort."
"Explain partitioning. What's quick sort's worst case and how do you avoid it?"
"Quick sort vs merge sort: which would you use and when?"
Related: "Find the k-th smallest element" (quickselect uses the same partition).

Clarifying questions to ask

Is in-place required?
Does stability matter? (Quick sort isn't stable.)
Are there many duplicate values? (Suggests three-way partitioning.)
Any preference for pivot choice?

Follow-ups to expect

"What's the worst case and when does it happen?"
"Why is the average O(n log n)?"
"How much stack space?"
"Lomuto vs Hoare partitioning?"
"What about arrays with many duplicates?"
"Why is quick sort often faster than merge sort in practice?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview