Python Program to Implement Quick Sort

Quick Sort is one of the most widely used sorting algorithms in practice — Python's own sorted() doesn't use it (it uses Timsort), but Quick Sort is still a staple interview question because it teaches the divide-and-conquer pattern and the idea of partitioning around a pivot value.

The core idea: pick a "pivot" element, rearrange the array so everything smaller than the pivot comes before it and everything larger comes after, then recursively sort the two halves.

Python Program to Implement Quick Sort

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

    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quick_sort(left) + middle + quick_sort(right)


numbers = [33, 10, 55, 71, 29, 3, 18, 71]
print("Original:", numbers)
print("Sorted:", quick_sort(numbers))

Output:

Original: [33, 10, 55, 71, 29, 3, 18, 71]
Sorted: [3, 10, 18, 29, 33, 55, 71, 71]

---

In-Place Quick Sort (Lomuto Partition)

The version above is easy to read but allocates new lists at every recursive call. The classic textbook implementation sorts the array in place instead, using a partition step:

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 quick_sort_in_place(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pivot_index = partition(arr, low, high)
        quick_sort_in_place(arr, low, pivot_index - 1)
        quick_sort_in_place(arr, pivot_index + 1, high)
    return arr


numbers2 = [33, 10, 55, 71, 29, 3, 18, 71]
print("Sorted in place:", quick_sort_in_place(numbers2))

Output:

Sorted in place: [3, 10, 18, 29, 33, 55, 71, 71]

Quick Sort's average time complexity is O(n log n), matching merge sort, but its worst case is O(n²) — this happens when the pivot repeatedly ends up being the smallest or largest element, such as when sorting an already-sorted array with a naive "always pick the last element" pivot strategy. Random or median-of-three pivot selection avoids this in practice. Unlike merge sort, Quick Sort doesn't need extra array space for the in-place version, which is why it's often faster in real-world use despite the same average complexity.

---