Skip to content

Implementing Quicksort in Python - A Step-by-Step Guide

Updated: at 04:34 AM

Quicksort is one of the most efficient sorting algorithms and is based on the divide-and-conquer approach. It was developed by Tony Hoare in 1959 and is still commonly used today.

In this comprehensive guide, we will cover the following:

Table of Contents

Open Table of Contents

Overview of Quicksort

Quicksort is based on the divide-and-conquer approach for sorting an array. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. This continues until the base case of empty or single-element arrays is reached, which are inherently sorted.

The steps for quicksort are:

  1. Select the pivot element
  2. Partition the array into two sub-arrays based on the pivot
  3. Recursively sort the sub-arrays

Some key properties of quicksort:

These characteristics make quicksort very fast for a variety of applications from sorting user data to complex machine learning algorithms.

Implementing Quicksort in Python

Let’s now go through a step-by-step implementation of the quicksort algorithm in Python.

1. Select the Pivot Element

There are different ways to choose the pivot:

For simplicity, we will start with always picking the last element as the pivot:

def quicksort(arr):
  # always use last element as pivot
  pivot = arr[len(arr) - 1]

2. Partition the Array

This involves iterating through the array and swapping elements such that those less than the pivot are placed before elements greater than the pivot.

We will use a pointer i that increments left to right, while swapping elements less than the pivot to the front of the array.

def quicksort(arr):

  pivot = arr[len(arr) - 1]

  i = 0
  for j in range(len(arr) - 1):
    if arr[j] < pivot:
      arr[i], arr[j] = arr[j], arr[i]
      i += 1

  arr[i], arr[len(arr)-1] = arr[len(arr)-1], arr[i]

The final swap places the pivot element between the two partitions.

3. Recursively Sort Sub-arrays

We simply call quicksort recursively on the slices from 0 to i-1 (left partition) and i+1 to the end (right partition).

def quicksort(arr):

  # pivot selection and partition


Putting it all together, the full quicksort implementation is:

def quicksort(arr):
  if len(arr) <= 1:
    return arr

  pivot = arr[len(arr) - 1]

  i = 0
  for j in range(len(arr)-1):
    if arr[j] < pivot:
      arr[i], arr[j] = arr[j], arr[i]
      i += 1

  arr[i], arr[len(arr)-1] = arr[len(arr)-1], arr[i]


  return arr

We added a base case to handle empty or single-element arrays to avoid infinite recursion.

Let’s test it on an example array:

arr = [4, 2, 7, 3, 1, 6]


# Output: [1, 2, 3, 4, 6, 7]

It correctly sorts the sample array!

Pivot Selection and Partitioning

Choosing the final element as pivot is simple but not optimal. Better alternatives include:

Median of Three Method

Pick median of first, middle and last elements as pivot:

def quicksort(arr):
  if len(arr) <= 1:
    return arr

  mid = len(arr) // 2

  if arr[0] < arr[mid]:
    if arr[mid] < arr[len(arr)-1]:
      pivot = arr[mid]
      pivot = arr[0]
    if arr[len(arr)-1] < arr[mid]:
      pivot = arr[mid]
      pivot = arr[len(arr)-1]

This reduces the chance of imbalanced partitions.

Random Pivot

Select a random index between 0 and length-1 as the pivot:

import random

# inside quicksort()
pivot_idx = random.randint(0, len(arr)-1)
pivot = arr[pivot_idx]

Randomness improves performance on already sorted or reversed arrays.

For partitioning, instead of swapping, we can keep track of the boundary point and only swap once. This reduces expensive swap operations.

def partition(arr, pivot):

  i = 0
  for j in range(len(arr)):
    if arr[j] < pivot:
      arr[j], arr[i] = arr[i], arr[j]
      i += 1

  arr[i], arr[len(arr)-1] = arr[len(arr)-1], arr[i]

  return i

Careful pivot selection and partitioning improves efficiency and avoids worst-case O(n^2) performance.

Time and Space Complexity Analysis

Time Complexity

Quicksort is very efficient on average. But worst-case occurs with poor pivots.

Space complexity

Quicksort sorts in-place requiring only O(log n) space for recursion stack.

Optimizations and Improvements

Some optimizations to further improve quicksort:

These optimizations make quicksort faster and more robust in different scenarios.

Comparison with Other Sorts

Merge Sort

Merge has better worst-case but requires more space. Useful if stability is needed.

Heap Sort

Good alternative if quicksort’s worst-case is unacceptable.

Intro Sort

Introsort combines advantages of both quicksort and heapsort.

So quicksort is preferred in most cases, but alternatives have tradeoffs to consider.

Usage Examples and Applications

Quicksort is extensively used due to its excellent performance:

It’s one of the most popular sorting algorithms used in practice across domains.


Some practice questions to test your quicksort skills:

  1. Implement quicksort with a random pivot and hoare partitioning scheme.

  2. Track the number of comparisons and swaps your quicksort algorithm makes.

  3. Modify quicksort to detect and handle duplicate elements.

  4. Combine quicksort with insertion sort to create a hybrid algorithm.

  5. Implement 3-way quicksort partitioning.


In this comprehensive guide, we implemented quicksort in Python from scratch, discussed key concepts like pivot selection and partitioning schemes, analyzed complexity, compared tradeoffs with other sorts, saw real-world applications, and worked through examples.

Quicksort is one of the fastest sorting algorithms due to its excellent divide-and-conquer approach. With some careful optimizations, it can be made even faster and adaptable for all kinds of sorting problems. Understanding quicksort provides a solid foundation in algorithmic thinking that is applicable across technical domains.

The implementation techniques, analysis, optimizations and examples covered in this guide will help prepare you for technical interviews. Quicksort remains a popular interview topic and being thorough with its concepts will give you an edge.

There are always opportunities to enhance the quicksort algorithm further through multi-threading, cache optimizations, hybrid schemes and more. I hope this guide provided a comprehensive overview and starting point for mastering quicksort in Python.