Quick Sort Algorithm: Complete Study Notes

1. Introduction and Problem Context

Quick Sort is a highly efficient, in-place sorting algorithm categorized under Divide and Conquer paradigms. While Merge Sort also achieves an optimal $O(N \log N)$ time complexity, Merge Sort requires an auxiliary temporary array resulting in $O(N)$ extra space. Quick Sort, on the other hand, operates completely in-place, using only the recursion stack space.

Why Learn All Sorting Algorithms?

Even when advanced algorithms like Quick Sort or Merge Sort exist, understanding every sorting algorithm is critical. Interviewers frequently build upon fundamental sorting mechanics to solve complex array and matrix problems.

2. Core Mental Model and Real-Life Analogy

High-Level Philosophy

Quick Sort relies on a single dominant operation: partitioning.

1. Pick a Pivot: Select any arbitrary element from the dataset to act as a reference point.
2. Correct Placement: Rearrange the dataset such that all elements smaller than the pivot reside on its left, and all elements larger reside on its right.
3. Recursive Sub-division: Treat the left and right sub-arrays independently and apply the exact same logic recursively until the base case of single-element arrays is reached.

3. Step-by-Step Algorithm Breakdown

The step-by-step lifecycle of executing a single Quick Sort partition:

The Rules of Partitioning:

• Pivot Choice: Can be the first element, last element, median, or a random element. For simplicity, we choose the first element (array[low]).
• Pointer Mechanics:
  • I pointer starts at the left boundary (low) and scans right to find the first element greater than the pivot.
  • J pointer starts at the right boundary (high) and scans left to find the first element smaller than the pivot.
  • Swap elements at I and J when valid.
  • Stop when I and J cross each other (J overtakes I), then swap the pivot into its correct partition index (J).

4. Pointer Movement & Partition Dry Run

Let's trace the partition logic using the array: [4, 6, 2, 5, 7, 9, 1, 3] with low = 0 and high = 7.

• Pivot = 4 (at index 0)
• I starts at index 0 (value 4)
• J starts at index 7 (value 3)

Resulting Array State After Partition:

[1, 3, 2, 4, 7, 9, 5, 6]
           ^
    Pivot (4) is now in its exact sorted position.
    Left Sub-array: [1, 3, 2] (Indices low to partition_index - 1)
    Right Sub-array: [7, 9, 5, 6] (Indices partition_index + 1 to high)

5. Complete Pseudocode Architecture

Below is the language-independent pseudocode reflecting the recursive structure and partition logic.

Function QuickSort(array, low, high):
    If low < high:
        partitionIndex = Partition(array, low, high)
        QuickSort(array, low, partitionIndex - 1)
        QuickSort(array, partitionIndex + 1, high)

Function Partition(array, low, high):
    pivot = array[low]
    i = low
    j = high

    While i < j:
        // Find first element greater than or equal to pivot from left
        While array[i] <= pivot and i <= high - 1:
            i++
        
        // Find first element smaller than or equal to pivot from right
        While array[j] > pivot and j >= low + 1:
            j--
            
        If i < j:
            Swap(array[i], array[j])

    // Place pivot in its correct sorted position
    Swap(array[low], array[j])
    Return j

6. Production C++ Implementation

Here is the clean, C++ implementation matching the logic compiled and verified during the lecture:

#include <vector>
#include <iostream>

using namespace std;

class Solution {
private:
    int partition(vector<int>& arr, int low, int high) {
        int pivot = arr[low];
        int i = low;
        int j = high;

        while (i < j) {
            // Find element strictly greater than pivot on the left
            while (arr[i] <= pivot && i <= high - 1) {
                i++;
            }
            // Find element strictly smaller than pivot on the right
            while (arr[j] > pivot && j >= low + 1) {
                j--;
            }
            if (i < j) {
                swap(arr[i], arr[j]);
            }
        }
        // Swap pivot into its ultimate correct position (index j)
        swap(arr[low], arr[j]);
        return j;
    }

    void qs(vector<int>& arr, int low, int high) {
        if (low < high) {
            int pIndex = partition(arr, low, high);
            qs(arr, low, pIndex - 1);
            qs(arr, pIndex + 1, high);
        }
    }

public:
    vector<int> sortArray(vector<int>& nums) {
        qs(nums, 0, nums.size() - 1);
        return nums;
    }
};

7. Complexity Analysis

Time Complexity

• Best Case ($O(N \log N)$): Occurs when the pivot splits the array into two nearly equal halves at every recursive step. The recursion tree depth is $\log_2 N$, and scanning each level takes linear time $O(N)$.
• Average Case ($O(N \log N)$): Statistically expected performance under randomized or standard input distributions.
• Worst Case ($O(N^2)$): Occurs when the chosen pivot consistently happens to be the smallest or largest element (e.g., sorting an already sorted array when picking the first element as the pivot). This leads to an unbalanced recursion tree of height $N$.

Space Complexity

• Auxiliary Space: $O(1)$ (In-place sorting; no temporary arrays are constructed).
• Recursion Stack Space: $O(\log N)$ average stack depth due to recursive function calls.

8. Summary and Key Takeaways

• Divide and Conquer Paradigm: Quick Sort breaks arrays down by selecting a pivot, partitioning elements around it, and conquering sub-problems recursively.
• In-Place Efficiency: Unlike Merge Sort, Quick Sort does not require allocating temporary arrays, making it memory-efficient.
• Two-Pointer Scan Strategy: The I pointer scans right for elements greater than the pivot, while the J pointer scans left for elements smaller than the pivot.
• Partition Index Guarantee: When pointers cross (I >= J), swapping the pivot with array[J] locks the pivot into its exact final sorted position.
• Recursive Sub-arrays: Sorting continues independently on the left sub-array (low to pIndex - 1) and right sub-array (pIndex + 1 to high).
• Optimal Time Performance: Delivers an average and best-case time complexity of $O(N \log N)$.
• Assignment Milestone: Minor adjustments to pointer comparison conditions (<= vs >=) allow developers to easily invert sorting order from ascending to descending.