Loading…

mediumArraysSometimes asked

Quicksort 2 - Sorting (Partition)

Q: How do you solve Quicksort 2 - Sorting (Partition) using the Recursive Quicksort with Helper Arrays (Intended) approach?

When to use it: The intended solution — it reuses Quicksort 1's partition and makes the print points obvious. This is Quicksort 1's partition wrapped in recursion. For a sub-array, set `p = a[0]`, route the remaining elements into `left` (`< p`) and `right` (`≥ p`), then return `qsort(left) + [p] + qsort(right)`. **Why recursing both sides sorts the array.** After partitioning, `p` is in its final sorted position (everything left is smaller, everything right is larger). Recursively sorting each side places every element correctly, so the concatenation is fully sorted. This is the divide-and-conquer guarantee. **Why the print shows partially sorted state.** The print runs *after* `qsort(left)` and `qsort(right)` have returned, so `left` and `right` are already sorted when we stitch and print. The very first line printed is the deepest-left combine (the smallest sub-array to finish), and the very last is the top-level combine — the entire sorted array. Tracing `[5,8,1,3,7,9,2]` you get `2 3`, then `1 2 3`, then `7 8 9`, then `1 2 3 5 7 8 9`. **Why the `len ≤ 1` base case and the `> 1` print guard.** A sub-array of size 0 or 1 is already sorted, so we return immediately — this also stops the recursion. We skip printing singletons because the challenge only wants combines of genuine sub-arrays (length > 1), matching how partitions of size 1 don't represent real merge work. **Why route equals to one side.** Using `≥ p` for the right side guarantees every non-pivot element lands in exactly one bucket even when duplicates exist; dropping the equals case would silently lose elements. Time complexity: O(n log n) average, O(n²) worst. Space complexity: O(n log n) average.

Q: How do you solve Quicksort 2 - Sorting (Partition) using the In-Place Lomuto Quicksort (Space-Optimised) approach?

When to use it: Bring up when asked how production quicksort sorts without allocating arrays at every level. Instead of allocating helper lists, partition the current slice in place. Lomuto's scheme keeps a boundary `i`; scanning `j` over the slice, smaller-than-pivot elements are swapped toward the front, then the pivot is swapped into the boundary, which becomes its final index `pIdx`. Recurse on the two sub-slices. **Why it saves memory.** No new arrays per level — all work happens within the original array, so only the recursion stack costs space (`O(log n)` when balanced). This is what real library quicksorts do. **Why printing is trickier here.** The 'partially sorted concatenation' the challenge wants corresponds to the out-of-place combine. To reproduce the exact same printed lines, you'd print the slice `[lo..hi]` after both recursive calls return and only when its length > 1 — but the in-place pivot placement (and equal-element handling) can yield a different internal arrangement than the helper-array version. If the grader expects the specific helper-array order, prefer the first approach; use this one when only the final sorted array (or in-place behaviour) is being graded. Time complexity: O(n log n) average, O(n²) worst. Space complexity: O(log n) average (recursion stack).

Arrays & Hashing · 60 of 83 · 9 min

Using the partition logic from Quicksort 1, implement a recursive quicksort that fully sorts the array.

The pivot for each sub-array is its first element. After sorting a sub-array (combining its sorted left part, the pivot, and its sorted right part), print that sub-array — but only when it has more than one element.

The final line printed is the fully sorted array.

In plain English

Quicksort 1 placed one pivot. Quicksort 2 repeats that recursively: after partitioning, both the left and right sides are themselves sorted by the same routine, then stitched back together. Printing the stitched result after each recursive return lets you watch the array assemble itself bottom-up, smallest pieces first.

Examples

Example 1

Input: arr = [5, 8, 1, 3, 7, 9, 2]
Output: 2 3 1 2 3 7 8 9 1 2 3 5 7 8 9
Note: Pivot 5 → left [1,3,2], right [8,7,9]. Sorting the left sub-array prints '2 3' then '1 2 3'; sorting the right prints '7 8 9'; the top-level combine prints the full sorted array.

Example 2

Input: arr = [4, 5, 3, 7, 2]
Output: 2 3 5 7 2 3 4 5 7
Note: Pivot 4 → left [3,2] sorts to '2 3'; right [5,7] sorts to '5 7'; top combine prints '2 3 4 5 7'.

Constraints

1 ≤ n ≤ 1000
-1000 ≤ arr[i] ≤ 1000
Elements are distinct in the challenge inputs
Pivot is always the first element of the current sub-array

Clarifying questions4First question: Do I recurse on both sides?Explore questions

Q1.Do I recurse on both sides?
Yes. Quicksort 1 partitions once; Quicksort 2 recursively sorts both the left and right partitions.
Q2.When exactly do I print?
After combining sort(left) + [pivot] + sort(right), and only when that combined array has more than one element.
Q3.What is the base case?
A sub-array of length 0 or 1 is already sorted — return it as-is and do not print.
Q4.Where does an element equal to the pivot go?
Pick a consistent side (here ≥ pivot goes right). The challenge inputs are distinct, but a consistent rule prevents losing duplicates in general.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Take the partition step from Quicksort 1 and apply it recursively: pivot = first element, split into left (< pivot) and right (≥ pivot), recursively sort each, then combine as `sort(left) + [pivot] + sort(right)`. Print the combined sub-array after each combine whose length is greater than 1. Base case: a sub-array of length ≤ 1 is already sorted (and is not printed).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can compose the single partition step into a correct recursion with a proper base case, and reason about the order in which sub-arrays become sorted.

Where candidates slip

Recursing on only one side, missing the length ≤ 1 base case (infinite recursion or printing singletons), or printing the raw partition before the recursive calls return.

How to stand out

Explain that printing after the combine shows partially sorted state, identify that the deepest-left combine prints first, and note the O(n²) worst case when the pivot is always the min/max.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Recursive Quicksort with Helper Arrays (Intended)	`O(n log n) average, O(n²) worst`	`O(n log n) average`	The intended solution — it reuses Quicksort 1's partition and makes the print points obvious.	Read
2	In-Place Lomuto Quicksort (Space-Optimised)Optimal	`O(n log n) average, O(n²) worst`	`O(log n) average (recursion stack)`	Bring up when asked how production quicksort sorts without allocating arrays at every level.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Recursion tree of quicksort

How to read it:Each node partitions; prints happen on the way back up, smallest sorted pieces first.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Recursive Quicksort with Helper Arrays (Intended)

TimeO(n log n) average, O(n²) worstSpaceO(n log n) average

The intended solution — it reuses Quicksort 1's partition and makes the print points obvious.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You already have a one-step partition. What if each side were itself partitioned the same way?

2Hint 2Explore hint

Write a function that partitions around arr[0] into left (<p) and right (≥p), then returns sort(left) + [p] + sort(right).

3Hint 3Explore hint

Add the base case len ≤ 1 (return as-is). Print the combined result right before returning, only when its length > 1.

A · Core idea

This is Quicksort 1's partition wrapped in recursion. For a sub-array, set p = a[0], route the remaining elements into left (< p) and right (≥ p), then return qsort(left) + [p] + qsort(right).

Why recursing both sides sorts the array. After partitioning, p is in its final sorted position (everything left is smaller, everything right is larger). Recursively sorting each side places every element correctly, so the concatenation is fully sorted. This is the divide-and-conquer guarantee.

Why the print shows partially sorted state. The print runs after qsort(left) and qsort(right) have returned, so left and right are already sorted when we stitch and print. The very first line printed is the deepest-left combine (the smallest sub-array to finish), and the very last is the top-level combine — the entire sorted array. Tracing [5,8,1,3,7,9,2] you get 2 3, then 1 2 3, then 7 8 9, then 1 2 3 5 7 8 9.

Why the `len ≤ 1` base case and the `> 1` print guard. A sub-array of size 0 or 1 is already sorted, so we return immediately — this also stops the recursion. We skip printing singletons because the challenge only wants combines of genuine sub-arrays (length > 1), matching how partitions of size 1 don't represent real merge work.

Why route equals to one side. Using ≥ p for the right side guarantees every non-pivot element lands in exactly one bucket even when duplicates exist; dropping the equals case would silently lose elements.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [5, 8, 1, 3, 7, 9, 2]

Array state

print 1

[3,2] sorted

[0]

[1]

Current pointerResolved stateNot processed

Final result2 3 / 1 2 3 / 7 8 9 / 1 2 3 5 7 8 9

C · Code with teaching comments

Reference implementation previewList<Integer> output = new ArrayList<>(); public int[] quickSort(int[] arr) { List<Integer> input = new ArrayList<>(); for (int x : arr) input.add(x);Explore the full code

solution.javaJava

Recursive Quicksort with Helper Arrays (Intended) — reference

4 teaching notes

1
List<Integer> output = new ArrayList<>();
2
 
3
public int[] quickSort(int[] arr) {
4
    List<Integer> input = new ArrayList<>();
5
    for (int x : arr) input.add(x);
6
    List<Integer> sorted = qsort(input);
7
    return sorted.stream().mapToInt(Integer::intValue).toArray();
8
}
9
 
10
private List<Integer> qsort(List<Integer> a) {
11
    // Base case: size 0 or 1 is already sorted — also stops the recursion. Not printed.
12
    if (a.size() <= 1) return a;
13
    int p = a.get(0);
14
    List<Integer> left = new ArrayList<>();
15
    List<Integer> right = new ArrayList<>();
16
    for (int i = 1; i < a.size(); i++) {
17
        if (a.get(i) < p) left.add(a.get(i));
18
        else right.add(a.get(i));
19
    }
20
    // Recurse on the left FIRST, so its prints appear before the right and before this
21
    // level's combine.
22
    List<Integer> res = new ArrayList<>(qsort(left));
23
    res.add(p);
24
    res.addAll(qsort(right));
25
    if (res.size() > 1) {
26
        StringBuilder sb = new StringBuilder();
27
        for (int i = 0; i < res.size(); i++) {
28
            if (i > 0) sb.append(' ');
29
            sb.append(res.get(i));
30
        }
31
        System.out.println(sb);
32
    }
33
    return res;
34
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.34 lines

D · Why it works and complexityO(n log n) average, O(n²) worst timeO(n log n) average spaceOpen the invariant and proofExplore the proof

Quicksort is 'partition, then trust recursion for both halves'. The print order is a free visualisation of the call stack unwinding — leaves resolve first, the root last. Recognising that post-order print = bottom-up assembly is the same insight behind printing a merge sort's merges.

ComplexityO(n log n) average, O(n²) worst time, O(n log n) average space — Each level of recursion does O(n) partition work across all sub-arrays; with balanced pivots there are O(log n) levels → O(n log n). A sorted input with first-element pivots gives one-sided splits, O(n) levels → O(n²). Helper arrays plus recursion stack cost O(n log n) space on average.

E · Edge cases and pitfalls6arr = [4, 5, 3, 7, 2] — Prints '2 3', then '5 7', then '2 3 4 5 7'.Explore edge cases

Edge cases handled

arr = [4, 5, 3, 7, 2]Prints '2 3', then '5 7', then '2 3 4 5 7'.
arr = [1, 2, 3]Already sorted; first-element pivots give one-sided splits — prints '2 3' then '1 2 3' (O(n²) shape).

Pitfalls

Recursing on only one side — leaves the other side unsorted.
Missing the len ≤ 1 base case — infinite recursion or stack overflow.
Printing the raw partition before the recursive calls return — prints unsorted instead of sorted sub-arrays.
Printing length-1 sub-arrays — violates the 'only length > 1' rule.

03.2

Approach 2 of 2 · Optimal

In-Place Lomuto Quicksort (Space-Optimised)

TimeO(n log n) average, O(n²) worstSpaceO(log n) average (recursion stack)

Bring up when asked how production quicksort sorts without allocating arrays at every level.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Can you sort without building new left/right lists at each level?

2Hint 2Explore hint

Partition the sub-array [lo..hi] in place around a pivot, returning the pivot's final index pIdx.

3Hint 3Explore hint

Recurse on [lo..pIdx-1] and [pIdx+1..hi]. Print the sub-array slice after both recursive calls if hi - lo + 1 > 1.

A · Core idea

Instead of allocating helper lists, partition the current slice in place. Lomuto's scheme keeps a boundary i; scanning j over the slice, smaller-than-pivot elements are swapped toward the front, then the pivot is swapped into the boundary, which becomes its final index pIdx. Recurse on the two sub-slices.

Why it saves memory. No new arrays per level — all work happens within the original array, so only the recursion stack costs space (O(log n) when balanced). This is what real library quicksorts do.

Why printing is trickier here. The 'partially sorted concatenation' the challenge wants corresponds to the out-of-place combine. To reproduce the exact same printed lines, you'd print the slice [lo..hi] after both recursive calls return and only when its length > 1 — but the in-place pivot placement (and equal-element handling) can yield a different internal arrangement than the helper-array version. If the grader expects the specific helper-array order, prefer the first approach; use this one when only the final sorted array (or in-place behaviour) is being graded.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [4, 5, 3, 7, 2]

Array state

before

pivot = 4

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final resultFinal sorted: 2 3 4 5 7

C · Code with teaching comments

solution.javaJava

In-Place Lomuto Quicksort (Space-Optimised) — optimal

3 teaching notes

1
public int[] quickSort(int[] arr) {
2
    sort(arr, 0, arr.length - 1);
3
    return arr;
4
}
5
 
6
private void sort(int[] a, int lo, int hi) {
7
    // Base case: slice of size 0 or 1 needs no work.
8
    if (lo >= hi) return;
9
    // Pivot lands at its final sorted index in place.
10
    int pIdx = partition(a, lo, hi);
11
    // Recurse on the left slice; pivot itself is already placed and excluded.
12
    sort(a, lo, pIdx - 1);
13
    sort(a, pIdx + 1, hi);
14
}
15
 
16
private int partition(int[] a, int lo, int hi) {
17
    int pivot = a[lo];
18
    int i = lo;
19
    for (int j = lo + 1; j <= hi; j++) {
20
        if (a[j] < pivot) {
21
            i++;
22
            int t = a[i]; a[i] = a[j]; a[j] = t;
23
        }
24
    }
25
    int t = a[lo]; a[lo] = a[i]; a[i] = t;
26
    return i;
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(n log n) average, O(n²) worst timeO(log n) average (recursion stack) spaceOpen the invariant and proofExplore the proof

The choice between out-of-place and in-place quicksort is the classic time/space-vs-clarity trade. Helper arrays make the partition and print points obvious; in-place Lomuto is leaner but its intermediate states differ. Pick the version that matches what's being graded.

ComplexityO(n log n) average, O(n²) worst time, O(log n) average (recursion stack) space — In-place partition is O(length) per call; balanced recursion gives O(n log n) total, degenerate pivots give O(n²). Only the recursion stack uses extra space: O(log n) average, O(n) worst.

E · Edge cases and pitfalls5arr = [1, 2, 3] — Sorted input → pivot always the min → fully one-sided recursion, O(n²) but correct: [1,2,3].Explore edge cases

Edge cases handled

arr = [1, 2, 3]Sorted input → pivot always the min → fully one-sided recursion, O(n²) but correct: [1,2,3].
arr = [3, 2, 1]Reverse sorted → still sorts correctly to [1,2,3] in O(n²).

Pitfalls

Using lo >= hi vs lo > hi inconsistently — both work, but mixing them causes off-by-one bugs.
Forgetting to exclude the pivot index when recursing (sort(lo, pIdx) loops forever).
Expecting identical printed intermediate lines to the helper-array version — the in-place arrangement can differ.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int[] quickSort(int[] arr) { sort(arr, 0, arr.length - 1); return arr; } Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Printing before recursion (wrong order)

The challenge wants the partially SORTED sub-array. Printing right after partition shows the raw, unsorted split instead.

Explore the code comparison

Don't write this

p = a[0]
left = [x for x in a[1:] if x < p]
right = [x for x in a[1:] if x >= p]
print(' '.join(map(str, left + [p] + right)))  # raw split
res = qsort(left) + [p] + qsort(right)
return res

Write this instead

p = a[0]
left = [x for x in a[1:] if x < p]
right = [x for x in a[1:] if x >= p]
res = qsort(left) + [p] + qsort(right)
if len(res) > 1:
    print(' '.join(map(str, res)))  # sorted sub-array
return res

Missing the base case

Without returning on len ≤ 1, the recursion never bottoms out and singletons also get printed, violating the spec.

Explore the code comparison

Don't write this

def qsort(a):
    p = a[0]            # crashes / recurses forever on []
    ...

Write this instead

def qsort(a):
    if len(a) <= 1:
        return a
    p = a[0]
    ...

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Recursive quicksort built on the single-partition step

Code pattern to memorize

def qsort(a):
    if len(a) <= 1: return a
    p = a[0]
    left  = [x for x in a[1:] if x < p]
    right = [x for x in a[1:] if x >= p]
    res = qsort(left) + [p] + qsort(right)
    print(res)        # only fires for len(res) > 1
    return res

Rules to remember

1Recurse on both sides — that is the only difference from Quicksort 1, which partitions once.
2Print the combined array after the recursive calls return, so what you print is partially (sub-)sorted, not raw.
3Only print when the combined sub-array has length > 1; length-1 sub-arrays are base cases and are never printed.
4Pivot is the first element of each sub-array; route equals consistently (here ≥ pivot goes right) so no element is lost.
5The LAST printed line is always the fully sorted array (the top-level combine).

Use this pattern when

You must fully sort and also show intermediate progress of a divide-and-conquer sort
Demonstrating how partition composes into a sort
A teaching / tracing context where each merge of sorted halves is observable

Choose another pattern when

You only need one partition, not a sort → Quicksort 1
You need guaranteed O(n log n) worst case → heapsort or mergesort, not quicksort
You only need the k-th element → quickselect (recurse one side)

Interview takeaway

Quicksort = partition + recurse on both halves. Printing each combine reveals the divide-and-conquer tree: small sorted pieces appear first, the full array last.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternDivide and conquer via partition. Quicksort = partition (place a pivot) + recurse on both sides. Average O(n log n); worst O(n²) with poor pivots. Printing each post-order combine visualises the recursion unwinding bottom-up.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Quicksort 1 - Partition
The single partition step this recursion is built on.
Running Time of Quicksort
Coming soon
Count comparisons/shifts to compare quicksort against insertion sort empirically.
Kth Largest Element (Quickselect)
Coming soon
Same partition, but recurse into only the side containing the target rank — O(n) average.

Same pattern

←

Quicksort 1 - Partition

Continue · Next problem

The Full Counting Sort

mediumArraysSometimes asked

Quicksort 2 - Sorting (Partition)

Arrays & Hashing · 60 of 83 · 9 min

Using the partition logic from Quicksort 1, implement a recursive quicksort that fully sorts the array.

The final line printed is the fully sorted array.

In plain English

Examples

Example 1

Input: arr = [5, 8, 1, 3, 7, 9, 2]
Output: 2 3 1 2 3 7 8 9 1 2 3 5 7 8 9
Note: Pivot 5 → left [1,3,2], right [8,7,9]. Sorting the left sub-array prints '2 3' then '1 2 3'; sorting the right prints '7 8 9'; the top-level combine prints the full sorted array.

Example 2

Input: arr = [4, 5, 3, 7, 2]
Output: 2 3 5 7 2 3 4 5 7
Note: Pivot 4 → left [3,2] sorts to '2 3'; right [5,7] sorts to '5 7'; top combine prints '2 3 4 5 7'.

Constraints

1 ≤ n ≤ 1000
-1000 ≤ arr[i] ≤ 1000
Elements are distinct in the challenge inputs
Pivot is always the first element of the current sub-array

Clarifying questions4First question: Do I recurse on both sides?Explore questions

Q1.Do I recurse on both sides?
Yes. Quicksort 1 partitions once; Quicksort 2 recursively sorts both the left and right partitions.
Q2.When exactly do I print?
After combining sort(left) + [pivot] + sort(right), and only when that combined array has more than one element.
Q3.What is the base case?
A sub-array of length 0 or 1 is already sorted — return it as-is and do not print.
Q4.Where does an element equal to the pivot go?
Pick a consistent side (here ≥ pivot goes right). The challenge inputs are distinct, but a consistent rule prevents losing duplicates in general.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can compose the single partition step into a correct recursion with a proper base case, and reason about the order in which sub-arrays become sorted.

Where candidates slip

Recursing on only one side, missing the length ≤ 1 base case (infinite recursion or printing singletons), or printing the raw partition before the recursive calls return.

How to stand out

Explain that printing after the combine shows partially sorted state, identify that the deepest-left combine prints first, and note the O(n²) worst case when the pivot is always the min/max.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Recursive Quicksort with Helper Arrays (Intended)	`O(n log n) average, O(n²) worst`	`O(n log n) average`	The intended solution — it reuses Quicksort 1's partition and makes the print points obvious.	Read
2	In-Place Lomuto Quicksort (Space-Optimised)Optimal	`O(n log n) average, O(n²) worst`	`O(log n) average (recursion stack)`	Bring up when asked how production quicksort sorts without allocating arrays at every level.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Recursion tree of quicksort

How to read it:Each node partitions; prints happen on the way back up, smallest sorted pieces first.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Recursive Quicksort with Helper Arrays (Intended)

TimeO(n log n) average, O(n²) worstSpaceO(n log n) average

The intended solution — it reuses Quicksort 1's partition and makes the print points obvious.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You already have a one-step partition. What if each side were itself partitioned the same way?

2Hint 2Explore hint

Write a function that partitions around arr[0] into left (<p) and right (≥p), then returns sort(left) + [p] + sort(right).

3Hint 3Explore hint

Add the base case len ≤ 1 (return as-is). Print the combined result right before returning, only when its length > 1.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [5, 8, 1, 3, 7, 9, 2]

Array state

print 1

[3,2] sorted

[0]

[1]

Current pointerResolved stateNot processed

Final result2 3 / 1 2 3 / 7 8 9 / 1 2 3 5 7 8 9

C · Code with teaching comments

solution.javaJava

Recursive Quicksort with Helper Arrays (Intended) — reference

4 teaching notes

1
List<Integer> output = new ArrayList<>();
2
 
3
public int[] quickSort(int[] arr) {
4
    List<Integer> input = new ArrayList<>();
5
    for (int x : arr) input.add(x);
6
    List<Integer> sorted = qsort(input);
7
    return sorted.stream().mapToInt(Integer::intValue).toArray();
8
}
9
 
10
private List<Integer> qsort(List<Integer> a) {
11
    // Base case: size 0 or 1 is already sorted — also stops the recursion. Not printed.
12
    if (a.size() <= 1) return a;
13
    int p = a.get(0);
14
    List<Integer> left = new ArrayList<>();
15
    List<Integer> right = new ArrayList<>();
16
    for (int i = 1; i < a.size(); i++) {
17
        if (a.get(i) < p) left.add(a.get(i));
18
        else right.add(a.get(i));
19
    }
20
    // Recurse on the left FIRST, so its prints appear before the right and before this
21
    // level's combine.
22
    List<Integer> res = new ArrayList<>(qsort(left));
23
    res.add(p);
24
    res.addAll(qsort(right));
25
    if (res.size() > 1) {
26
        StringBuilder sb = new StringBuilder();
27
        for (int i = 0; i < res.size(); i++) {
28
            if (i > 0) sb.append(' ');
29
            sb.append(res.get(i));
30
        }
31
        System.out.println(sb);
32
    }
33
    return res;
34
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.34 lines

D · Why it works and complexityO(n log n) average, O(n²) worst timeO(n log n) average spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6arr = [4, 5, 3, 7, 2] — Prints '2 3', then '5 7', then '2 3 4 5 7'.Explore edge cases

Edge cases handled

arr = [4, 5, 3, 7, 2]Prints '2 3', then '5 7', then '2 3 4 5 7'.
arr = [1, 2, 3]Already sorted; first-element pivots give one-sided splits — prints '2 3' then '1 2 3' (O(n²) shape).

Pitfalls

Recursing on only one side — leaves the other side unsorted.
Missing the len ≤ 1 base case — infinite recursion or stack overflow.
Printing the raw partition before the recursive calls return — prints unsorted instead of sorted sub-arrays.
Printing length-1 sub-arrays — violates the 'only length > 1' rule.

03.2

Approach 2 of 2 · Optimal

In-Place Lomuto Quicksort (Space-Optimised)

TimeO(n log n) average, O(n²) worstSpaceO(log n) average (recursion stack)

Bring up when asked how production quicksort sorts without allocating arrays at every level.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Can you sort without building new left/right lists at each level?

2Hint 2Explore hint

Partition the sub-array [lo..hi] in place around a pivot, returning the pivot's final index pIdx.

3Hint 3Explore hint

Recurse on [lo..pIdx-1] and [pIdx+1..hi]. Print the sub-array slice after both recursive calls if hi - lo + 1 > 1.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [4, 5, 3, 7, 2]

Array state

before

pivot = 4

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final resultFinal sorted: 2 3 4 5 7

C · Code with teaching comments

solution.javaJava

In-Place Lomuto Quicksort (Space-Optimised) — optimal

3 teaching notes

1
public int[] quickSort(int[] arr) {
2
    sort(arr, 0, arr.length - 1);
3
    return arr;
4
}
5
 
6
private void sort(int[] a, int lo, int hi) {
7
    // Base case: slice of size 0 or 1 needs no work.
8
    if (lo >= hi) return;
9
    // Pivot lands at its final sorted index in place.
10
    int pIdx = partition(a, lo, hi);
11
    // Recurse on the left slice; pivot itself is already placed and excluded.
12
    sort(a, lo, pIdx - 1);
13
    sort(a, pIdx + 1, hi);
14
}
15
 
16
private int partition(int[] a, int lo, int hi) {
17
    int pivot = a[lo];
18
    int i = lo;
19
    for (int j = lo + 1; j <= hi; j++) {
20
        if (a[j] < pivot) {
21
            i++;
22
            int t = a[i]; a[i] = a[j]; a[j] = t;
23
        }
24
    }
25
    int t = a[lo]; a[lo] = a[i]; a[i] = t;
26
    return i;
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(n log n) average, O(n²) worst timeO(log n) average (recursion stack) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5arr = [1, 2, 3] — Sorted input → pivot always the min → fully one-sided recursion, O(n²) but correct: [1,2,3].Explore edge cases

Edge cases handled

arr = [1, 2, 3]Sorted input → pivot always the min → fully one-sided recursion, O(n²) but correct: [1,2,3].
arr = [3, 2, 1]Reverse sorted → still sorts correctly to [1,2,3] in O(n²).

Pitfalls

Using lo >= hi vs lo > hi inconsistently — both work, but mixing them causes off-by-one bugs.
Forgetting to exclude the pivot index when recursing (sort(lo, pIdx) loops forever).
Expecting identical printed intermediate lines to the helper-array version — the in-place arrangement can differ.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int[] quickSort(int[] arr) { sort(arr, 0, arr.length - 1); return arr; } Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Printing before recursion (wrong order)

The challenge wants the partially SORTED sub-array. Printing right after partition shows the raw, unsorted split instead.

Explore the code comparison

Don't write this

p = a[0]
left = [x for x in a[1:] if x < p]
right = [x for x in a[1:] if x >= p]
print(' '.join(map(str, left + [p] + right)))  # raw split
res = qsort(left) + [p] + qsort(right)
return res

Write this instead

p = a[0]
left = [x for x in a[1:] if x < p]
right = [x for x in a[1:] if x >= p]
res = qsort(left) + [p] + qsort(right)
if len(res) > 1:
    print(' '.join(map(str, res)))  # sorted sub-array
return res

Missing the base case

Without returning on len ≤ 1, the recursion never bottoms out and singletons also get printed, violating the spec.

Explore the code comparison

Don't write this

def qsort(a):
    p = a[0]            # crashes / recurses forever on []
    ...

Write this instead

def qsort(a):
    if len(a) <= 1:
        return a
    p = a[0]
    ...

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Recursive quicksort built on the single-partition step

Code pattern to memorize

def qsort(a):
    if len(a) <= 1: return a
    p = a[0]
    left  = [x for x in a[1:] if x < p]
    right = [x for x in a[1:] if x >= p]
    res = qsort(left) + [p] + qsort(right)
    print(res)        # only fires for len(res) > 1
    return res

Rules to remember

1Recurse on both sides — that is the only difference from Quicksort 1, which partitions once.
2Print the combined array after the recursive calls return, so what you print is partially (sub-)sorted, not raw.
3Only print when the combined sub-array has length > 1; length-1 sub-arrays are base cases and are never printed.
4Pivot is the first element of each sub-array; route equals consistently (here ≥ pivot goes right) so no element is lost.
5The LAST printed line is always the fully sorted array (the top-level combine).

Use this pattern when

You must fully sort and also show intermediate progress of a divide-and-conquer sort
Demonstrating how partition composes into a sort
A teaching / tracing context where each merge of sorted halves is observable

Choose another pattern when

You only need one partition, not a sort → Quicksort 1
You need guaranteed O(n log n) worst case → heapsort or mergesort, not quicksort
You only need the k-th element → quickselect (recurse one side)

Interview takeaway

Quicksort = partition + recurse on both halves. Printing each combine reveals the divide-and-conquer tree: small sorted pieces appear first, the full array last.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Quicksort 1 - Partition
The single partition step this recursion is built on.
Running Time of Quicksort
Coming soon
Count comparisons/shifts to compare quicksort against insertion sort empirically.
Kth Largest Element (Quickselect)
Coming soon
Same partition, but recurse into only the side containing the target rank — O(n) average.

Same pattern

←

Quicksort 1 - Partition

Continue · Next problem

The Full Counting Sort