Quick Sort

In the previous lesson, we studied Merge Sort, an efficient sorting algorithm based on the Divide and Conquer strategy.

Merge Sort gives predictable performance, but it requires extra memory.

In this lesson, we explore another powerful divide-and-conquer algorithm: Quick Sort.

Quick Sort is one of the most widely used sorting algorithms in real-world systems.

The Core Idea of Quick Sort

Quick Sort works by selecting a special element called a pivot.

The algorithm rearranges the array so that:

All elements smaller than the pivot come before it, and all elements larger than the pivot come after it.

Once the pivot is in its correct position, the same process is applied to the left and right subarrays.

This continues recursively until the entire array is sorted.

Why It Is Called “Quick” Sort

Quick Sort usually performs fewer comparisons than other sorting algorithms.

Although its worst-case time complexity is O(n²), in practice it performs extremely well because the average-case complexity is:

O(n log n)

This makes Quick Sort faster than Merge Sort in many real-world scenarios.

Choosing the Pivot

The choice of pivot is critical to Quick Sort’s performance.

A poor pivot choice (such as always picking the smallest element) can lead to unbalanced partitions and poor performance.

Common pivot strategies include:

• First element
• Last element
• Middle element
• Random element

Random or middle pivots usually give better performance.

Quick Sort Algorithm (Code)

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)

arr = [38, 27, 43, 3, 9, 82, 10]
print(quick_sort(arr))

This implementation is easy to understand and shows how partitioning works.

In-Place Quick Sort (Concept)

In practice, Quick Sort is often implemented in-place, meaning it does not use extra memory for new arrays.

Instead, elements are rearranged within the original array using pointers.

This makes Quick Sort memory efficient.

Time and Space Complexity

Average Time Complexity: O(n log n)

Worst-Case Time Complexity: O(n²) (rare with good pivot selection)

Space Complexity: O(log n) due to recursion stack.

Real-World Usage

Quick Sort is widely used in system libraries and production environments.

Languages like C, C++, and Java use variations of Quick Sort for built-in sorting.

It is preferred when:

Speed is critical and average performance matters more than worst-case guarantees.

Mini Practice

Think about this:

• Why does a bad pivot lead to poor performance?
• Why is Quick Sort often faster than Merge Sort in practice?

Exercises

Quick Quiz

In the next lesson, we will study Heap Sort and see how a heap-based structure can be used for efficient sorting.