Implementing the Quicksort Function in Python

Now that we have our pivot function ready, it’s time to implement Quicksort.

Quicksort is a recursive sorting algorithm that repeatedly uses the pivot to partition the list into smaller parts and then sorts each part.

The pivot function takes a list (or sublist) and:
- Rearranges elements so that all smaller elements are to the left.
- All larger elements are to the right.
- Returns the pivot index in its correct sorted position.
Quicksort then:
- Recursively calls itself on the left side of the pivot.
- Recursively calls itself on the right side of the pivot.

We first create a helper function to handle recursion with indices:

def quicksort_helper(lst, left, right):

if left < right: # Base case: stop when left >= right

pivot_index = pivot(lst, left, right) # Partition list and get pivot index

# Recursively sort left side

quicksort_helper(lst, left, pivot_index – 1)

# Recursively sort right side

quicksort_helper(lst, pivot_index + 1, right)

return lst

We can now wrap the helper function so users don’t need to pass indices:

def quicksort(lst):

return quicksort_helper(lst, 0, len(lst) - 1)

Let’s take an example list:

Step-by-step execution:

Initial call: quicksort_helper(my_list, 0, 6)
- Pivot = 4 → rearranges list → [2, 1, 3, 4, 6, 7, 5]
- Pivot index = 3
Left recursion: quicksort_helper(my_list, 0, 2)
- Pivot = 2 → [1, 2, 3]
- Pivot index = 1
- Left: [1] → already sorted
- Right: [3] → already sorted
Right recursion: quicksort_helper(my_list, 4, 6)
- Pivot = 6 → [5, 6, 7]
- Pivot index = 5
- Left: [5] → already sorted
- Right: [7] → already sorted
Combine results: Entire list is now sorted:

Pivot function is a helper that organizes elements and returns an index.
Base case: When left >= right, recursion stops.
In-place sorting: Quicksort modifies the original list.
Wrapping with a simple quicksort(lst) function avoids manually passing indices.