Skip to content

Mastering Quick Sort in Python: A Comprehensive Guide

Updated: at 01:47 AM

Quick sort is an efficient sorting algorithm that works by recursively dividing an array into smaller subarrays until they are fully sorted. Developed by Tony Hoare in 1959, quick sort adopts a divide-and-conquer approach to rearrange elements in an array relative to a pivot value.

The key steps involved in quick sort are:

  1. Select a pivot element from the array. This is usually done randomly.
  2. Partitioning: Rearrange the array into two subarrays such that all elements less than the pivot are moved to the left subarray, and all elements greater than the pivot are moved to the right subarray. The pivot element ends up in its final position.
  3. Recursively apply the above steps to the left and right subarrays until the entire array is sorted.

Quick sort has an average case time complexity of O(nlogn). However, its worst-case complexity is O(n^2) when the array is already sorted or contains many duplicate elements.

In this comprehensive Python tutorial, we will cover the following topics related to quick sort:

Table of Contents

Open Table of Contents

Pseudocode for Quick Sort

The pseudocode for the quick sort algorithm is as follows:

quickSort(array, leftIndex, rightIndex):

  if leftIndex < rightIndex:

    pivotIndex <- partition(array, leftIndex, rightIndex)

    quickSort(array, leftIndex, pivotIndex - 1)

    quickSort(array, pivotIndex + 1, rightIndex)

partition(array, leftIndex, rightIndex):

  set pivot to array[rightIndex]

  storeIndex <- leftIndex - 1

  for i from leftIndex to rightIndex - 1:

    if array[i] < pivot:

      swap array[i] and array[storeIndex]


  swap array[storeIndex+1] and array[rightIndex]

  return storeIndex + 1

This pseudocode depicts the high-level working of quick sort. It begins by checking the base case. If the left and right indexes have not crossed, it picks a pivot element and partitions the array around it such that elements less than the pivot are to the left and greater than pivot are to the right of it.

The partition() function handles this partitioning logic. It iterates through the array, compares each element with the pivot, and swaps elements such that lesser elements are moved to the left side of the pivot.

Once partitioned, quick sort is recursively called on the left and right subarrays. This recursion continues until the array is fully sorted.

Python Implementation of Quick Sort

Here is how quick sort can be implemented in Python:

def partition(arr, low, high):
  pivot = arr[high]
  i = low - 1

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

  arr[i+1], arr[high] = arr[high], arr[i+1]
  return i + 1

def quickSort(arr, low, high):
  if low < high:
    pi = partition(arr, low, high)
    quickSort(arr, low, pi-1)
    quickSort(arr, pi+1, high)

The key steps are:

  1. Choose the rightmost element as pivot
  2. Partition the array around the pivot
  3. Recursively sort the subarrays

To sort an array, we simply call quickSort(arr, 0, len(arr)-1).

Here is quick sort in action on an example array:

arr = [10, 7, 8, 9, 1, 5]
quickSort(arr, 0, len(arr)-1)

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

The key to implementing quick sort efficiently is the partition scheme. Many different partitioning methods are possible like Hoare partition, Lomuto partition, etc. The partition scheme shown above adopts the Lomuto partition approach.

Complexity Analysis of Quick Sort

Time Complexity

The time complexity of quick sort depends heavily on the pivot selection during partitioning.

So the pivot selection directly impacts the balance of partitions and recursion depth, driving quick sort’s time complexity.

Space Complexity

The base version of quick sort uses O(logn) additional space on the stack for recursive calls. But optimized in-place quick sort has a space complexity of O(1).

Lomuto vs Hoare Partition Schemes

The partition scheme I demonstrated above uses the Lomuto partition approach.

In Lomuto partitioning, the pivot is initially placed at the end of array. Elements lesser than pivot are placed to the left of it.

In Hoare partitioning, the pivot is initially placed at the start. Elements greater than pivot are moved to the right side.

Lomuto is generally preferred as it is simpler to implement and exhibits better performance by reducing swap operations. Hoare can suffer from worst-case O(n^2) runtime in some cases.

Comparison Between Quick Sort and Other Sorting Algorithms

Here is how quick sort compares to other popular sorting algorithms:

So quick sort provides optimal O(nlogn) time complexity on average while also being in-place. However, it is less stable than merge sort.

Optimizations to Improve Quick Sort Performance

There are a few ways to optimize quick sort and improve its performance:

Carefully selecting the pivot and partitioning scheme provides the biggest gains in optimizing quick sort.

Common Mistakes to Avoid

Here are some common mistakes to watch out for when implementing quick sort in Python:

Overall, pay close attention to pivot selection, partitioning logic, recursion handling and base cases to avoid these mistakes.

Applications of Quick Sort

Quick sort is widely used as an efficient sorting algorithm due to its optimal log-linear time complexity. Here are some common applications:

When to Use Quick Sort

Quick sort is a good sorting algorithm to use when:

However, quick sort is not ideal when:

So in summary, quick sort provides lightning fast performance for small to medium datasets while also minimizing space overhead. Just be mindful of pitfalls around duplicate elements.

Real-World Examples of Quick Sort

Here are some real-world examples of quick sort usage:


Quick sort is one of the most popular sorting algorithms used in practice due to its excellent O(nlogn) time complexity on average.

We learned how it adopts a divide-and-conquer approach by selecting a pivot and partitioning elements around it. Sorting is achieved by recursively sorting the subarrays.

An efficient implementation in Python requires careful selection of the pivot element and partitioning scheme. By picking the median pivot and using a technique like Hoare partition, we can optimize quick sort’s performance.

It works well for small and medium arrays where speed is important and stability is not required. The log-linear time complexity makes it well-suited for sorting large datasets. However, alternate algorithms may be better for sorted or duplicate data.

Quick sort will continue to be a staple of efficient sorting implementations due to its speed, minimal memory overhead, and adaptability using various optimizations. A solid understanding of this algorithm is key for any programmer.