Master QuickSort in Python: Step‑by‑Step Explanation, Code, and Optimizations

In the previous article we covered the first five common sorting algorithms; because quicksort is so important, this piece focuses solely on quicksort.

Algorithm Introduction

Sorting algorithms are among the oldest and most fundamental topics in computer science. To be a competent programmer you must understand various sorting methods, and quicksort, invented by Turing Award winner C. A. R. Hoare in 1960, is the most widely used due to its speed.

Algorithm Principle

Quicksort can be implemented in many ways; the following uses a simple divide‑and‑conquer iterative approach with three steps:

Choose an element in the array as the pivot (also called the comparison value).

Partition the array: elements smaller than the pivot go to the left side, larger ones to the right.

Recursively apply the first two steps to the left and right sub‑arrays until each sub‑array contains only one element.

Example array: {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}.

Select the middle element 26 as the pivot.

Compare each element with 26, placing smaller values on the left partition and larger values on the right, producing the second column in the diagram.

Recursively partition the left and right sub‑arrays, continuing until each sub‑array has a single element.

Combine results by concatenating left partition + pivot + right partition.

Code Implementation

quick_sort = lambda array: array if len(array) <= 1 else quick_sort([item for item in array[1:] if item <= array[0]]) + [array[0]] + quick_sort([item for item in array[1:] if item > array[0]])

This concise lambda version is impressive, but overusing lambda can hurt readability, and PEP 8 discourages it. A more readable, Pythonic version uses a regular function:

def quick_sort(arr):
    """Quick sort implementation"""
    if len(arr) < 2:
        return arr
    # Choose the middle element as pivot for easier understanding
    mid = arr[len(arr) // 2]
    # Remove pivot from the original list
    arr.remove(mid)
    left, right = [], []
    for item in arr:
        if item >= mid:
            right.append(item)
        else:
            left.append(item)
    return quick_sort(left) + [mid] + quick_sort(right)

Algorithm Analysis

Stability: Quicksort is unstable ; equal elements may not preserve their original order.

Type: It is a comparison sort .

Time complexity: O(n log n) on average.

Space complexity: O(n log n) due to recursive calls and auxiliary storage.

Comparison with mergesort: Both use divide‑and‑conquer, but mergesort splits the array directly in half and then merges, requiring additional sorting during merge, whereas quicksort partitions by comparison and concatenates without further sorting, making quicksort generally more efficient.

Quicksort Optimizations

Quicksort performs poorly on very small data sets. A common optimization is to use quicksort until partitions become small, then switch to insertion sort, which is near‑linear on nearly sorted data.

Run quicksort on the whole data set until it is almost sorted.

When a partition size falls below a threshold, stop quicksort and apply insertion sort to that partition.

This hybrid approach is proven to be more effective; future articles will benchmark these variations.

Interview Simulation

Interviewer: Do you know quicksort?

Candidate: A little.

Interviewer: Explain the algorithm.

Candidate: Choose a pivot, partition elements smaller to the left and larger to the right, then recursively apply the process to the sub‑arrays until each contains a single element.

Interviewer: What are its strengths and weaknesses?

Candidate: It handles large data sets well due to divide‑and‑conquer, but its performance degrades on small data sets.

Interviewer: How would you optimize it?

Candidate: Use quicksort for large partitions and switch to insertion sort for small ones.

Interviewer: Can you write it on the spot?

Candidate: (writes the lambda version shown above).

Conclusion

Quicksort is the most frequently asked sorting algorithm in interviews and exams; mastering it is essential. Practice the code, understand its principles, and share with peers.