Quick Sort Algorithm

Quick Sort is a fast divide-and-conquer sorting algorithm that partitions an array around a pivot and recursively sorts both sides.

What is Quick Sort?

Quick Sort is a comparison-based sorting algorithm that uses the divide-and-conquer strategy. It chooses an element called a pivot, rearranges the array so smaller elements go to one side and larger elements go to the other side, and then recursively sorts both sides.

The key operation in Quick Sort is partitioning. After partitioning, the pivot is placed in its final sorted position, even though the left and right sides may still need sorting.

Core Intuition

Quick Sort works by asking one powerful question: “Can we place one element exactly where it belongs?” That element is the pivot.

Once the pivot is placed correctly, every element smaller than the pivot is on its left, and every element greater than the pivot is on its right. Now the original problem has been split into two smaller sorting problems.

Quick Sort Algorithm Steps

1. Choose a pivot.
   A common approach is to choose the last element as the pivot.
2. Partition the array.
   Move elements smaller than or equal to the pivot to the left side.
3. Place the pivot correctly.
   Swap the pivot into the boundary position between smaller and larger elements.
4. Recursively sort the left side.
   Apply Quick Sort to the elements before the pivot.
5. Recursively sort the right side.
   Apply Quick Sort to the elements after the pivot.
6. Stop at base cases.
   A subarray with zero or one element is already sorted.

Interactive Quick Sort Visualization

Use the visualization below to see how Quick Sort chooses a pivot, scans the current subarray, swaps smaller elements to the left, and recursively sorts smaller partitions.

Dry Run Example

Suppose we want to sort:

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

First partition: pivot = 5

• Choose the last element, 5, as the pivot.
• Scan the array and move elements smaller than or equal to 5 to the left side.
• Only 1 is smaller than 5, so it is moved before the pivot.
• After partitioning → [1, 5, 8, 9, 10, 7]
• The pivot 5 is now fixed at index 1.

Sort the left side

• Left side is [1].
• It has one element, so it is already sorted.

Sort the right side: [8, 9, 10, 7]

• Choose 7 as the pivot.
• No element in [8, 9, 10] is smaller than 7.
• Place 7 at the beginning of this subarray → [1, 5, 7, 9, 10, 8]

Continue recursively

• Now sort [9, 10, 8].
• Choose 8 as pivot and place it first → [1, 5, 7, 8, 10, 9]
• Sort [10, 9] using pivot 9 → [1, 5, 7, 8, 9, 10]

The array is now sorted.

Quick Sort Code in Python

This implementation uses the Lomuto partition scheme, where the last element of the current subarray is chosen as the pivot.

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

        # Move elements smaller than or equal to pivot to the left side.
        for j in range(low, high):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]

        # Place pivot after the smaller elements.
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        return i + 1

    def sort(low, high):
        if low >= high:
            return

        pivot_index = partition(low, high)
        sort(low, pivot_index - 1)
        sort(pivot_index + 1, high)

    sort(0, len(arr) - 1)
    return arr


print(quick_sort([10, 7, 8, 9, 1, 5]))

Time and Space Complexity

When Should You Use Quick Sort?

Interview Notes and Common Pitfalls

This section highlights the key ideas interviewers expect you to understand, especially around pivot choice, partitioning, recursion, and worst-case behavior.

What interviewers may expect you to know

• Quick Sort is based on divide and conquer.
• The partition step places the pivot in its final sorted position.
• Average time complexity is O(n log n).
• Worst-case time complexity is O(n²).
• Quick Sort is usually in-place, depending on implementation.
• Standard Quick Sort is not stable.
• Randomized pivot selection reduces the chance of worst-case behavior.

Common mistakes

• Forgetting the base case low >= high.
• Returning the wrong pivot index after partitioning.
• Recursing on ranges that still include the pivot.
• Using a fixed pivot without discussing worst-case behavior.
• Confusing Quick Sort with Merge Sort: Quick Sort partitions first, then sorts recursively.
• Claiming Quick Sort is always O(n log n).

Related coding interview problems

• Sort an Array
• Kth Largest Element in an Array
• Kth Smallest Element
• Sort Colors
• Top K Frequent Elements

Quick Quiz

Key Takeaways

• Quick Sort uses divide and conquer.
• Partitioning is the core operation.
• After partitioning, the pivot is fixed in its final sorted position.
• Average time complexity is O(n log n).
• Worst-case time complexity is O(n²), usually due to poor pivot choices.
• Quick Sort is important for interview problems involving partitioning and kth element selection.