Python Program for Quick Sort Algorithm

A Python program for quick sort uses a partition function to divide the list and recursively sorts sublists; for example, 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).

Examples

Input[3, 1, 4, 1, 5]

Output[1, 1, 3, 4, 5]

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

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

Input[]

Output[]

How to Think About It

To sort a list quickly, pick a middle value called a pivot. Then split the list into three parts: numbers less than the pivot, numbers equal to the pivot, and numbers greater than the pivot. Sort the smaller parts by repeating the same steps until the list is fully sorted.

Algorithm

1

Check if the list has one or no elements; if yes, return it as sorted.

2

Choose the middle element as the pivot.

3

Create three lists: elements less than pivot, equal to pivot, and greater than pivot.

4

Recursively apply quick sort to the less and greater lists.

5

Combine the sorted less list, equal list, and sorted greater list and return.

Code

python

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)

print(quick_sort([3, 1, 4, 1, 5]))

Output

[1, 1, 3, 4, 5]

Dry Run

Let's trace quick_sort([3, 1, 4, 1, 5]) through the code

1

Initial call

arr = [3, 1, 4, 1, 5], pivot = 4

2

Partition

left = [3, 1, 1], middle = [4], right = [5]

3

Recursive call on left

quick_sort([3, 1, 1])

4

Left recursive partition

pivot = 1, left = [], middle = [1, 1], right = [3]

5

Recursive calls on left and right of left

quick_sort([]) returns [], quick_sort([3]) returns [3]

6

Combine left results

[] + [1, 1] + [3] = [1, 1, 3]

7

Recursive call on right

quick_sort([5]) returns [5]

8

Final combine

[1, 1, 3] + [4] + [5] = [1, 1, 3, 4, 5]

Call	Pivot	Left	Middle	Right	Result
[3,1,4,1,5]	4	[3,1,1]	[4]	[5]	[1,1,3,4,5]
[3,1,1]	1	[]	[1,1]	[3]	[1,1,3]
[]	-	-	-	-	[]
[3]	-	-	-	-	[3]
[5]	-	-	-	-	[5]

Why This Works

Step 1: Choosing the pivot

The pivot divides the list into smaller parts to sort separately, making sorting faster.

Step 2: Splitting the list

We split the list into three parts: less than, equal to, and greater than the pivot to organize elements.

Step 3: Recursion

Sorting the smaller parts by calling the same function again breaks the problem into easier pieces.

Step 4: Combining results

Joining the sorted parts gives the fully sorted list.

Alternative Approaches

In-place quick sort

python

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

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

arr = [3,1,4,1,5]
quick_sort_inplace(arr, 0, len(arr)-1)
print(arr)

This method sorts the list without extra space but is more complex to understand.

Using built-in sorted()

python

arr = [3,1,4,1,5]
sorted_arr = sorted(arr)
print(sorted_arr)

This is the simplest and fastest way in Python but does not teach the quick sort algorithm.

Complexity: O(n log n) time, O(n) space

Time Complexity

Quick sort divides the list and sorts sublists recursively, leading to average O(n log n) time. Worst case is O(n²) if pivot choices are poor.

Space Complexity

The recursive calls use stack space proportional to the depth, which is O(log n) on average. The simple recursive version also uses extra space for new lists, making it O(n).

Which Approach is Fastest?

In-place quick sort is faster and uses less memory but is harder to implement; the simple recursive version is easier to understand but uses more space.

Approach	Time	Space	Best For
Simple recursive quick sort	O(n log n) average	O(n) due to new lists	Learning and clarity
In-place quick sort	O(n log n) average	O(log n) stack space	Performance and memory efficiency
Built-in sorted()	O(n log n)	O(n)	Practical use without learning algorithm