Quick Sort

Question 1

What is the "Partition" step in Quick Sort?

Accepted Answer

Rearranging smaller/pivot/larger — Partitioning places the pivot in its correct sorted position, with all smaller elements to its left and all larger elements to its right.

Question 2

What is quicksort's AVERAGE-case time complexity?

Accepted Answer

O(n log n), balanced splits — With reasonably balanced partitions, quicksort recurses log n deep doing O(n) partitioning per level: O(n log n) on average.

Question 3

What is quicksort's WORST-case time complexity, and when does it occur?

Accepted Answer

O(n²), unbalanced splits — If the pivot is always the smallest/largest element, one side has n−1 elements, giving depth n and O(n²). Already-sorted input with a first/last-element pivot triggers this.

Question 4

Quicksort follows which paradigm?

Accepted Answer

A divide-and-conquer paradigm — It partitions around a pivot so that left ≤ pivot ≤ right, then recursively sorts the two partitions — divide and conquer.

Question 5

What is quicksort's auxiliary SPACE complexity (typical in-place version)?

Accepted Answer

O(log n) recursion stack — Partitioning is in place, but recursion uses stack space proportional to depth: O(log n) average, O(n) worst (mitigated by recursing into the smaller side first).

Question 6

Is the standard quicksort stable?

Accepted Answer

No, swaps distant equal elements — Long-range swaps during partitioning can reorder equal keys, so quicksort is not stable by default.

Question 7

How does randomized pivot selection help quicksort?

Accepted Answer

Makes the O(n²) case unlikely — Choosing a random pivot means no specific input reliably triggers worst-case behavior; expected time is O(n log n) with high probability.

Question 8

The 'median-of-three' pivot strategy picks the median of…

Accepted Answer

The first, mid, last elements — Taking the median of first/middle/last gives a better pivot estimate cheaply and avoids the O(n²) trap on sorted/reverse-sorted inputs.

Question 9

Why is quicksort often faster in practice than merge sort despite the same average complexity?

Accepted Answer

In-place gives cache locality — Quicksort works in place with sequential memory access and tight inner loops, beating merge sort's O(n) buffer and extra copying on typical in-memory arrays.

Question 10

The Lomuto vs Hoare partition schemes differ in that Hoare's…

Accepted Answer

Two pointers, fewer swaps — Hoare's two-ended partition does about 3× fewer swaps on average than Lomuto's single-direction scheme, though it's slightly trickier to implement correctly.

Quick Sort Algorithm

Quick Sort: Level 0 (partition)

Partition around a pivot

Test your knowledge

What is the "Partition" step in Quick Sort?

The short version

In more depth

Partitioning is Key

When to reach for this

Interview Questions

References & Further Reading

Love this visualization?