Quick sort in Python

Why it matters

Quick sort is one of the best-known sorting methods. Many sorting libraries use a version of it, and it is often fast for lists of numbers in memory. Python's own sorted() and list.sort() do not use quick sort. They use a method called Timsort, which is built from merge sort ideas. You will still meet quick sort in interviews, and the technique behind it, called partitioning, shows up in many problems that have nothing to do with sorting. If you can partition a list around a value, you can solve problems about the k-th largest item, the odd items moved to one side, and more.

Quick sort also has a weakness that interviewers like to ask about. On some inputs it becomes very slow, and in Python it can stop with a RecursionError. This lesson shows both sides: how the method works, why it is fast on average, and how the bad case happens and how to prevent it.

You need the divide and conquer idea and the recursion pattern from the first two lessons of this module. Merge sort divides the work before it solves the halves. Quick sort does the opposite: most of its work happens while it divides, and the join step is free.

The idea from first principles

Imagine you must sort a hand of playing cards with no tools. A simple plan is this. Pick one card at random and call it the pivot. Sort the other cards into two piles: cards smaller than the pivot go on the left, and cards bigger than the pivot go on the right. Now look at the pivot. It sits between the two piles, and every card on its left is smaller and every card on its right is bigger. The pivot is already in its final place, and you never need to move it again.

Next, sort the left pile in the same way, and sort the right pile in the same way. Each pile is a smaller sorting problem of the same kind, so you call the same method on it. When a pile has zero or one card, it is already sorted, and that is the base case.

The three steps in divide and conquer language are:

1. Partition: choose a pivot and rearrange the list so smaller values are on its left and bigger values on its right. The pivot is now in its final position.
2. Conquer: sort the left part and the right part by calling quick sort on each.
3. Combine: nothing. The two parts are already in the right place relative to each other.

Compare this with merge sort. Merge sort splits the list by position, sorts the halves, and does the real work when it merges them. Quick sort splits the list by value, so the pieces are already in order relative to each other, and the combine step has no work left. Both methods use recursion and both divide the problem. They put the work in different places.

The partition step

Partitioning is the heart of quick sort, so study it carefully. The version below is called the Lomuto partition, after the computer scientist who popularized it. It uses the last item in the range as the pivot. It keeps one marker, called i, that always points to the last item of the "smaller" zone. A second marker, j, scans the rest of the range.

Read the code, then read the explanation that follows it.

def partition(a, lo, hi):
    pivot = a[hi]
    i = lo - 1                              # end of the "smaller" zone
    for j in range(lo, hi):
        if a[j] < pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]       # put the pivot in its place
    return i + 1

Here are the Python details that matter in this code:

• lo and hi are both index positions, and both are included in the range. range(lo, hi) stops one step before hi, so the loop never touches the pivot.
• a[i], a[j] = a[j], a[i] swaps two items. Python builds the pair on the right side first, then stores it back. You do not need a temporary variable, and you do not need a separate swap function.
• The function changes the list you pass in. It does not make a copy. This is why the function returns only an index, not a new list.

Start with i one position before the range, so the smaller zone is empty. The loop moves j from the first item to the item just before the pivot. Each time a[j] is smaller than the pivot, the function grows the smaller zone by one (i += 1) and swaps the new item into it. Items that are not smaller are left alone, so they stay in the bigger zone that is forming to the right. When the loop ends, everything from lo to i is smaller than the pivot, and everything from i + 1 to hi - 1 is bigger or equal. The last swap puts the pivot at i + 1, between the two zones. The function returns that index, which is the pivot's final position.

Each item is compared with the pivot exactly once. So one partition of n items costs about n comparisons. That cost is the same as one level of merge sort, and the difference lies in how the levels add up.

Worked example 1: partitioning step by step

Partition the list [10, 7, 8, 9, 1, 5]. The last value, 5, is the pivot. Follow the variables i and j one at a time.

• Start: i is -1. The scan begins at j equal to 0.
• j = 0: a[0] is 10. Is 10 less than 5? No. Nothing changes.
• j = 1: a[1] is 7. No. Nothing changes.
• j = 2: a[2] is 8. No.
• j = 3: a[3] is 9. No.
• j = 4: a[4] is 1. Yes, 1 is less than 5. Move i to 0 and swap a[0] with a[4]. The list becomes [1, 7, 8, 9, 10, 5].
• The scan ends before index 5, which holds the pivot. The last step puts the pivot in place: swap a[1] with a[5]. The list becomes [1, 5, 8, 9, 10, 7].
• The function returns 1. The pivot 5 is at index 1, with 1 on its left and everything bigger on its right.

Notice that the values on the right of the pivot are not sorted yet. Only the pivot has found its final place.

Now watch a full quick sort run with the visualizer. It shows the pivot, the scan, and the recursive calls on the two sides.

While you watch, look for one fact: after each partition, the pivot never moves again. Each call finishes its own pivot and then hands the two sides to smaller calls. When every side has one item or none, the whole list is sorted.

Worked example 2: the full sort and its recursion

Here is the complete quick sort, with the partition from the previous section. The code sorts the list [10, 7, 8, 9, 1, 5].

The output is:

[1, 5, 7, 8, 9, 10]

Notice the two recursive calls. The first sorts lo to p - 1, which is everything left of the pivot. The second sorts p + 1 to hi, which is everything right of the pivot. The pivot is excluded from both, because it is already in its final place. Including it can cause an endless loop, which the mistakes section explains.

The next program prints each pivot as its partition finishes, with the list at that moment. The indentation shows the recursion depth. The " " * depth part repeats a string: " " * 2 is four spaces.

The output is:

pivot 5 is now at index 1: [1, 5, 8, 9, 10, 7]
  pivot 7 is now at index 2: [1, 5, 7, 9, 10, 8]
    pivot 8 is now at index 3: [1, 5, 7, 8, 10, 9]
      pivot 9 is now at index 4: [1, 5, 7, 8, 9, 10]
final [1, 5, 7, 8, 9, 10]

Read the trace from the top. The first partition places 5. The left side has only the value 1, which needs no work. The right side is 8 9 10 7, and its last value 7 becomes the next pivot, so 7 goes to index 2. The right side of that is 9 10 8, so 8 becomes the next pivot, and so on. Each line places exactly one pivot, and each line has one more indent than the one above it. The value 1 never appears as a pivot: a single item is already in place, and the base case returns without printing.

Time: average and worst case

Now the important analysis. The running time depends on where the pivot lands, because the pivot splits the list into two parts, and the sizes of those parts decide how many levels the recursion has.

If every pivot splits the list into two halves, the recursion has about log n levels, the same as merge sort. Each level partitions all the items once, costing about n comparisons. Total: n times log n. This is the average case for a random input with a good pivot, and the name O(n log n) describes it.

The bad case happens when the pivot is always the smallest or biggest item in its range. Then one part is empty and the other part has everything except the pivot. The recursion has n levels instead of log n. Each level still does about n work, so the total is n times n, which is O(n squared).

When does that happen? Take a list that is already sorted, and always choose the last item as the pivot. The last item is the biggest value, so the partition puts it at the very end, and the left side holds everything else. The next level does the same thing to that left side. Here is a program that counts the comparisons for a sorted list and for a random list, both with 500 items. The counting is done inside the partition. The function uses the global keyword, which tells Python that comparisons is the variable defined at the top of the file, not a new variable inside the function.

The output is:

sorted input: 124750 comparisons
random input: 5000 comparisons

The sorted input took 124,750 comparisons. That number is exactly 499 times 500 divided by 2, which is the sum 499 + 498 + ... + 1. Each partition removes just one item from the problem, so the sizes shrink by one each time instead of by half. The random input took 5,000 comparisons, which is far fewer. The random numbers come from a generator with the seed 1, so the output is the same each time you run this program with Python 3.14.

The bad case grows fast. With 500 items the sorted list needs about 25 times as many comparisons as the random list. With 2,000 items the sorted list hits the recursion limit, which the next sections explain.

Choosing a better pivot

The fix for sorted input is to stop choosing the last item. Choose a pivot at random, and swap it into the last position before partitioning. Then no fixed pattern in the input can make every pivot the worst one. The next program does this with a seeded random number generator. rng.randint(lo, hi) returns a whole number from lo up to and including hi. A seed is a starting number for the generator. The same seed gives the same sequence of random numbers, so the program behaves the same way on every run.

The output is:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

The two inputs in this test are the ones that were slow before. Now both finish quickly, because the random pivot almost always lands near the middle. The expected cost with a random pivot is O(n log n), and no input can force the bad case except by bad luck, which becomes very unlikely as n grows.

The swap a[r], a[hi] = a[hi], a[r] moves the chosen item into the last position. After that, the same partition function works without any change.

Other fixes exist. Some libraries pick the median of three values: they look at the first, middle and last items and use the middle value of those three as the pivot. On sorted input, that median is the middle item, so the split is balanced. A person who knows the method can still build an input that defeats it, which is why the random pivot is the standard answer in interviews.

Duplicates: the three-way partition

Quick sort has a second weak spot. When many items are equal to the pivot, the Lomuto partition puts them all on one side, and the recursion becomes lopsided. A three-way partition handles that case. It splits the range into three zones: smaller than the pivot, equal to it, and bigger. The equal zone is already in its final place, so the recursion skips it entirely.

The next program sorts a small list with many repeated values. Then it sorts 1,000 random values that are only 0, 1 or 2. It checks the second result against Python's own sorted().

The output is:

[1, 1, 2, 2, 2, 2, 3, 3]
1000 values from 0 to 2 sorted correctly: True

Read the loop carefully. The zone from lo to lt - 1 holds values smaller than the pivot. The zone from lt to i - 1 holds values equal to the pivot. The zone from gt + 1 to hi holds values bigger than the pivot. The item at i is the next one to inspect. When it is smaller, it moves into the left zone. When it is bigger, it moves into the right zone, and i does not advance, because the swapped-in item has not been checked yet. When it equals the pivot, it stays where it is. When the loop ends, the middle zone is final, and the two recursive calls sort only the outer zones.

With many equal values, the middle zone can be large, and the recursion skips all of it. That is why the three-way version stays fast when the data has few distinct values.

Quick select: finding the k-th smallest item

Partitioning can answer a question without sorting everything. Suppose you want the third smallest value in a list. Partition around a pivot. If the pivot lands at index 2, it is the answer. If it lands at a larger index, the answer is on the left, so you can ignore the right side completely. If it lands at a smaller index, the answer is on the right. Each step keeps one side and throws the other away, which is the halving pattern from the first lesson of this module.

This method is called quick select. Its average time is O(n), because the first partition costs n, the next costs about n / 2, and the total is less than 2n. The version below reads the list and the rank k from the keyboard. The rank is counted from 1, so k equal to 1 means the smallest item. The function uses 0-based indexes inside, so it subtracts 1 from k.

This program reads input, so it is not a run-in-place example. Save it as quick_select.py and run it with python3 quick_select.py. Type the lines when the program asks for them, or pipe them in from a shell with printf.

def partition(a, lo, hi):
    pivot = a[hi]
    i = lo - 1
    for j in range(lo, hi):
        if a[j] < pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]
    return i + 1
 
 
def quick_select(a, lo, hi, k):
    """Return the item that would sit at index k (0-based) if a were sorted."""
    while True:
        if lo == hi:
            return a[lo]
        p = partition(a, lo, hi)
        if k == p:
            return a[p]
        if k < p:
            hi = p - 1
        else:
            lo = p + 1
 
 
n = int(input())
items = [int(x) for x in input().split()]
rank = int(input())
print(f"item at rank {rank} is {quick_select(items, 0, n - 1, rank - 1)}")

Type these lines when the program asks, one line at a time:

6
7 10 4 3 20 15
3

The output is:

item at rank 3 is 7

Check it by hand. Sorted, the list is 3 4 7 10 15 20, and the third item is 7. The function never sorted the whole list. It only kept the side that held index 2 at each step. Change the last line to 1 and the answer becomes 3, the smallest item.

Notice the structure of quick_select. It uses a loop instead of recursion, because each step keeps only one side. The while True loop ends with a return when the pivot lands on the wanted index, or when the range has one item left. The int(x) for x in input().split() line is a list comprehension. It builds the list of numbers from the words on one line.

What happens inside: the call stack

Each call to a function gets its own frame, which is a small block of memory that holds the function's local variables. Quick sort's recursion stacks these frames. Each quick_sort frame holds lo, hi and p. The first recursive call runs in a new frame on top of the caller's frame. When it returns, the second call runs in its own frame.

On average, the pivot splits the list in the middle, so the stack is about log n frames deep. That is small. On the bad sorted input, the first call's left side has almost everything, so the stack grows as deep as the number of items.

Python limits how deep the stack can grow. You can check the limit with sys.getrecursionlimit(). In a normal Python 3.14 session it returns 1000. When a call would go past the limit, Python stops the program with a RecursionError. A list of 2,000 items sorted with the last value as the pivot needs about 2,000 frames, so it hits the limit.

You can raise the limit with sys.setrecursionlimit(). That is not a good fix. Each frame still uses memory, and a very high limit can crash the interpreter itself. The better fix is to change the pivot choice and the order of the recursive calls, as the next two sections show.

Memory for the list is separate. The partition only swaps values inside the list, so it needs a few variables and no second list. That is why quick sort is called in-place: it sorts without making a second list as big as the input.

Recursing into the smaller side

The plain recursion on sorted input goes deep, because one side is almost empty and the other holds nearly everything. A simple change fixes the depth. After partitioning, recurse only on the smaller side, and handle the bigger side with a loop that reuses the same variables. The smaller side has at most half of the items, so each recursive call works on at most half of its parent's range. That keeps the depth at about log n, no matter how bad the pivots are.

The next program compares the two versions on a sorted list of 2,000 items. It records the deepest call that each version reaches. The plain version recurses on both sides, so it hits the recursion limit and stops. The smaller-side version recurses only on the smaller side and loops on the rest. The try and except lines catch the error, so the program can print a message and go on.

The output is:

plain: RecursionError: maximum recursion depth exceeded
smaller side first: deepest call 1
second sorted: True

The plain version fails on this input. The smaller-side version finishes, and its deepest call is depth 1. On sorted input with the last value as pivot, the right side is always empty, so the smaller side is the empty right side. Its call returns at once, and the loop handles the rest without going deeper.

The smaller-side version does not make the running time faster. It is still O(n squared) for this bad pivot choice. It protects you from the recursion limit, but not from the slow running time. For the running time, you still need a random pivot.

Quick sort versus Python's built-in sort

Here is a comparison to remember. Both methods are divide and conquer, but they differ in the places that matter for real projects.

In everyday Python code, call sorted() or list.sort(). They are fast, they are stable, and they have a guaranteed O(n log n) worst case. Write quick sort yourself when you need to learn partitioning, when you need a partition for a different task, or when an interview asks for it.

Stability is the main difference in behavior. The next section shows the effect.

Why quick sort is not stable

A sort is stable when equal items keep their input order. Quick sort does not guarantee that, because the partition swaps items across the list. Watch this small example. Each item is a pair of a key and an id. The sort compares only the key, and the input has two items with key 2, in the order id 1 then id 3.

Trace the partition by hand. The pivot is the last item, (2, 3), with key 2. The scan finds (1, 2), which is smaller, and swaps it to the front. Then the final swap moves the pivot into place by swapping it with (2, 1). The item (2, 1) lands after the pivot, so id 3 now comes before id 1.

The program below runs the quick sort on those pairs. It then runs Python's built-in sort on a copy of the same pairs, which keeps the order of equal keys.

The output is:

key 1 id 2
key 2 id 3
key 2 id 1
[(1, 2), (2, 1), (2, 3)]

The two items with key 2 changed order in the quick sort. The built-in sort kept them in the input order: id 1 before id 3. The key=lambda r: r[0] part tells the built-in sort to compare only the first item of each pair. A lambda is a short function written in one line.

If a user sorted a table by name and then sorted by grade, quick sort could break the name order inside each grade. Use sorted(), which is stable, when that matters.

Common mistakes and the errors they cause

Quick sort has a few traps, and two of them produce serious errors. One of them is special to Python.

Mistake 1: the recursion limit is reached on sorted input. Sorting 2,000 items that are already in order, with the last value as the pivot, makes the recursion deeper than the limit of 1,000. The code is short, and the output is an error:

def quick_sort(a, lo, hi):
    if lo >= hi:
        return
    p = partition(a, lo, hi)
    quick_sort(a, lo, p - 1)
    quick_sort(a, p + 1, hi)
 
 
data = list(range(2000))
quick_sort(data, 0, len(data) - 1)

The end of the error message looks like this. The file path and line numbers depend on where you saved the file, and the first lines of the traceback are left out here:

    quick_sort(a, lo, p - 1)
    ~~~~~~~~~~^^^^^^^^^^^^^^
  File "...", line 41, in quick_sort
    quick_sort(a, lo, p - 1)
    ~~~~~~~~~~^^^^^^^^^^^^^^
  [Previous line repeated 995 more times]
  File "...", line 40, in quick_sort
    p = partition(a, lo, hi)
RecursionError: maximum recursion depth exceeded

The message names the function that kept calling itself. The line [Previous line repeated 995 more times] shows the repeated calls. The fix is the random pivot from earlier, plus recursing into the smaller side first. The program is not wrong about the answer. It runs out of frames before it can finish.

Mistake 2: recursing on the pivot too. If you write quick_sort(a, lo, p) instead of quick_sort(a, lo, p - 1), the left call includes the pivot. The pivot is the biggest item on the left side, so the call partitions again, puts the pivot back at the end, and calls itself on the same range. It never ends, and you get the same RecursionError as before:

def bad_pivot_included(a, lo, hi):
    if lo >= hi:
        return
    p = partition(a, lo, hi)
    bad_pivot_included(a, lo, p)
    bad_pivot_included(a, p + 1, hi)
 
 
bad_pivot_included([3, 1, 2], 0, 2)

The last line of the output is RecursionError: maximum recursion depth exceeded. The rule is simple: after a partition, exclude index p from both calls.

Mistake 3: forgetting the final swap. Without the swap that puts the pivot in place, the list is wrong, and Python gives no error. The debugging walkthrough below shows this bug.

Mistake 4: many equal values with the Lomuto partition. The sort is correct, but it becomes slow, because equal values all go to one side. Eight equal values need 28 comparisons with the Lomuto partition. The number is 7 plus 6 plus ... plus 1. Use the three-way partition when your data has many repeats.

Mistake 5: a negative index that wraps around. In Python, a[-1] means the last item, not an error. If an index becomes -1 by accident, the code reads or changes the wrong item, and nothing stops it. The program below calls the partition on an empty range, where hi is -1. The range 0 to -1 has no items, but the function still reads a[hi] and swaps:

def partition(a, lo, hi):
    pivot = a[hi]
    i = lo - 1
    for j in range(lo, hi):
        if a[j] < pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]
    return i + 1
 
 
data = [3, 1, 2]
p = partition(data, 0, -1)
print("returned", p, "data", data)

The output is:

returned 0 data [2, 1, 3]

No error appears. The list changed from [3, 1, 2] to [2, 1, 3]. In Java, the same index would stop the program with an error. In Python it does not, so the base case if lo >= hi matters more here. Keep it, and check your indexes when a result looks odd.

Debugging walkthrough: a sort that leaves a value at the end

Suppose a teammate wrote a partition with the final swap missing. The function runs, returns an index, and the output is wrong. Here is the broken code, followed by the output it prints for the list from earlier.

def broken_sort(a, lo, hi):
    if lo >= hi:
        return
    pivot = a[hi]
    i = lo - 1
    for j in range(lo, hi):
        if a[j] < pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    p = i + 1
    broken_sort(a, lo, p - 1)
    broken_sort(a, p + 1, hi)
 
 
data = [10, 7, 8, 9, 1, 5]
broken_sort(data, 0, len(data) - 1)
print(data)

The output is:

[1, 7, 8, 9, 10, 5]

The output is wrong in an obvious way: the 5 is at the end, and the 7 is before it. Do not start by rereading the whole function. Ask a narrow question: where did the pivot go? The pivot was 5, and it is still at index 5, the last position. The partition returned index 1, so the function treated index 1 as the pivot's place, but it never moved the 5 there. The missing step is the swap a[i + 1], a[hi] = a[hi], a[i + 1].

That is the method to use with any sorting bug. First, find one value that is out of place. Second, find where that value was supposed to go. Third, follow only the code that moves that value. A single print after each partition, as in the trace program above, would have shown the 5 staying at the end in one line of output.

Interview questions and real-world uses

Interviewers test quick sort in a few predictable ways.

• "What is the average and worst-case time?" Average O(n log n), worst O(n squared). Explain the bad case, which is a bad pivot on sorted input, and how a random pivot avoids it.
• "Why is quick sort popular if its worst case is worse?" It sorts in place, uses little extra memory, and has a small constant factor. Explain that the average case matters more in practice, and that randomizing the pivot makes the worst case very rare.
• "Find the k-th largest item." Use quick select, and explain why its average time is O(n) rather than O(n log n).
• "Make quick sort stable." Say that a standard quick sort is not stable, and that you would use sorted() instead, or add the index as a tie-breaker in the comparison.
• "Partition a list so the odd numbers come first." Use the same partition idea with a different test in the comparison.

Python's built-in sort is stable and has an O(n log n) worst case. Many other languages use quick sort inside their libraries, with safeguards such as a random or median pivot, or a switch to another method when the recursion gets deep. Knowing that real libraries guard against the worst case is a good interview point.

Practice

Try each exercise on your own before you open the solution.

1. Trace the first partition of [3, 6, 2, 8, 1] with the last value as pivot. Write the list after each swap. Hint: the pivot is 1, so no value is smaller, and only the last swap moves anything.

2. Change quick_sort so the pivot is the first item instead of the last. Explain what must change. Hint: swap the first item into the last position before partition runs.

3. Find the smallest item in the rotated list [4, 5, 6, 7, 0, 1, 2] with quick select, using k equal to 0. Explain why this works even though the list is not fully sorted. Hint: quick select only needs the answer's position, not a full sort.

4. Count the comparisons that quick sort makes on [1, 2, 3] with the last value as pivot. Hint: the first partition makes 2 comparisons, and the next levels make the rest.

5. Write a function that moves all zeros to the front of a list and keeps the other values in any order. Use one partition with the test a[j] == 0. Hint: the partition in this lesson uses <, so think about which zone should hold zeros.

6. Change quick_sort so it recurses first into the smaller side and loops on the bigger side. Explain why the recursion depth is then at most log n. Hint: each recursive call works on at most half the items.

7. Find the number of comparisons for quick sort on a list of 8 equal values with the Lomuto partition, and explain why it is large. Hint: after each partition, how many items are left on the left side?

8. Explain in words why the pivot is excluded from both recursive calls. Hint: think about what would happen if it were included and the partition placed it again.

9. Write a function that returns True if a list contains two equal values, using sorting. Hint: sort a copy first, then compare each value with the next one.

10. A teammate sorts 50,000 random numbers with quick sort and it finishes quickly. They then sort the same numbers after they were already sorted. Explain what happens, using the words pivot and worst case. Hint: the last value of a sorted list is the largest.

Show the answer

1. Start with [3, 6, 2, 8, 1]. The pivot is 1. Nothing is smaller than 1, so i stays at -1 for the whole scan. The final swap exchanges index 0 (the value 3) with index 4 (the value 1), giving [1, 6, 2, 8, 3]. The pivot 1 is now at index 0, with nothing on its left and the rest on its right. The function returns 0.

Show the answer

2. Inside quick_sort, before calling partition, swap a[lo] with a[hi]. The partition function stays the same, because it still uses the last item as the pivot. Keep the swap in quick_sort, not in partition, so the partition code is simpler to test.

Show the answer

3. Call quick_select(values, 0, len(values) - 1, 0). For [4, 5, 6, 7, 0, 1, 2] it returns 0. Quick select does not need a sorted list. Each partition puts every smaller value on the left of the pivot, and the function keeps only the side that holds index 0. The smallest item is found without sorting the rest.

Show the answer

4. For [1, 2, 3], the pivot is 3. The scan compares 1 with 3 and 2 with 3, which is 2 comparisons. The pivot stays at the end. The left side [1, 2] has pivot 2, which makes 1 comparison. The total is 3 comparisons.

Show the answer

5. Use i = -1 and loop over range(len(a)). When a[j] equals 0, increase i, swap a[i] with a[j], and continue. At the end the zeros are at the front. For [3, 0, 2, 0, 1, 0] the result is [0, 0, 0, 3, 1, 2]. You do not need a final pivot swap, because this task has no pivot.

Show the answer

6. Write the recursion so the call on the smaller side comes first, and the call on the bigger side is a loop that sets lo to p + 1 or hi to p - 1. Each call that recurses works on at most half of its range, so the depth is at most log n. The loop does not add a frame.

Show the answer

7. With 8 equal values and the Lomuto partition, no value is less than the pivot, so the pivot stays at the end and the left side has 7 items. The next level has 6, and so on. The total is 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 comparisons. Equal values make the Lomuto partition as slow as a sorted list.

Show the answer

8. The pivot is already in its final place after the partition. If it were included, the recursion would partition the same range again, the partition would place it again, and the calls would never shrink the range. Excluding it guarantees that each call works on fewer items.

Show the answer

9. Sort a copy of the list, then loop from index 0 to len(s) - 2 and compare each value with the next one. If two neighbors are equal, return True. Otherwise return False at the end. Sorting first makes equal values sit next to each other. For [4, 2, 9, 2] the function returns True, and for [1, 2, 3] it returns False.

Show the answer

10. A random list gives a pivot near the middle, so the recursion is about log n levels deep. A sorted list with the last value as pivot always gives the largest value as the pivot, so every split is lopsided, and the recursion goes n levels deep. The sorted case is the worst case for this pivot choice. In Python it does not just get slow. The recursion goes about 50,000 levels deep, far past the limit of 1,000, so the program stops with RecursionError. A random pivot fixes both problems. With random.Random(42) and values up to 1,000,000, a random list of 50,000 values took 931,245 comparisons with the last value as pivot.

What you now know

• Quick sort chooses a pivot, partitions the range so smaller values are on the left and bigger values on the right, and sorts each side.
• The partition places the pivot in its final position. The two recursive calls exclude that position.
• Average time is O(n log n). The worst case is O(n squared), which happens when the pivot is always the smallest or biggest value.
• A random pivot prevents sorted input from causing the worst case. A three-way partition handles many duplicates.
• Quick select finds the k-th smallest item in O(n) average time by keeping only the side that holds the answer.
• Quick sort sorts in place, but it is not stable. Use sorted() in everyday code, because it is stable and has a guaranteed O(n log n) worst case.
• A RecursionError on sorted input means the recursion went deeper than the limit of 1,000. Check the pivot choice and the order of the recursive calls.