Quick Sort

About

Quick Sort chooses a single element from the array to act as a pivot. It then rearranges the rest of the array so that every element smaller than the pivot goes to its left, and every element larger goes to its right—a process called partitioning. Once the pivot sits securely in its final correct spot, the algorithm recursively repeats this exact process on the left and right unsorted islands until everything is locked into place.

Complexities

• Time complexity:

  • Best / Average Case: $O(n\log n)$ (When the chosen pivot splits the data relatively evenly, creating a balanced recursion tree)
    
    
  • Worst Case: $O(n^2)$ (When the pivot choices are terrible—like always picking the smallest or largest element in an already sorted or reverse-sorted array. This causes the recursion tree to become completely skewed, reducing it to linear scanning)
    
    

• Space complexity: $O(\log n)$

Code Implementation

Last Element as Pivot:

![[quicksort.mp4]]

def quick_sort(nums, low, high):
    # If low is less than high
    if low < high:
        # Partition the input list using the partition function and store the returned "middle" index
        middle = partition(nums, low, high)
        
        # Recursively call quick_sort on the elements left of the pivot (low to middle - 1)
        quick_sort(nums, low, middle - 1)
        
        # Recursively call quick_sort on the elements right of the pivot (middle + 1 to high)
        quick_sort(nums, middle + 1, high)

def partition(nums, low, high):
    # Set pivot to the element at index high
    pivot = nums[high]
    
    # Set i to the index before low
    i = low - 1
    
    # For each index (j) in range(low, high)
    for j in range(low, high):
        # If the element at index j is less than the pivot
        if nums[j] < pivot:
            # Increment i by 1
            i += 1
            # Swap the element at index i with the element at index j
            nums[i], nums[j] = nums[j], nums[i]
            
    # Swap the element at index i + 1 with the element at index high (the pivot's position)
    nums[i + 1], nums[high] = nums[high], nums[i + 1]
    
    # Return i + 1 (the pivot's new index)
    return i + 1

First Element as Pivot (Video):

![[quk.mp4]]

def quick_sort(nums, low, high):
    # If low is less than high
    if low < high:
        # Partition the input list using the partition function and store the returned "middle" index
        middle = partition(nums, low, high)
        
        # Recursively call quick_sort on the elements left of the pivot (low to middle - 1)
        quick_sort(nums, low, middle - 1)
        
        # Recursively call quick_sort on the elements right of the pivot (middle + 1 to high)
        quick_sort(nums, middle + 1, high)
        
def partition(nums, low, high):
    # 1. Set pivot to the FIRST element in the current range
    pivot = nums[low]
    
    # 2. i starts at low (the pivot's original index)
    i = low 
    
    # 3. Loop j from low + 1 to the end of the range
    for j in range(low + 1, high + 1):
        # If the current element is less than the pivot
        if nums[j] < pivot:
            i += 1  # Expand the "smaller than pivot" section
            nums[i], nums[j] = nums[j], nums[i]  # Swap it into place
            
    # 4. Final Swap: Place the pivot into its correct middle position (index i)
    nums[low], nums[i] = nums[i], nums[low]
    
    # Return the pivot's new permanent index
    return i

Key Takeaways

• The Pivot Dependency: The efficiency of Quick Sort rests entirely on pivot choices. If you blindly pick the last element of an already sorted array, it hits the disastrous $O(n^2)$ worst case. Real-world implementations avoid this by picking a random pivot or choosing the Median-of-Three (the median value among the first, middle, and last elements).
  
  

• Cache Friendly: Even though Quick Sort shares the same $O(n\log n)$ average case as Merge Sort, it is almost always significantly faster in practice on physical hardware. Why? Because it operates in-place without copying data to extra arrays, staying confined to contiguous blocks of memory which leverages the CPU's cache layout flawlessly.
  
  

• When to Use It:

  • It is the default sorting choice for many language standard libraries (like the primitive arrays sorting in Java) because of its exceptional real-world speed and minimal memory footprint.
    
    
  • Avoid it if you require guaranteed worst-case timelines or strict algorithm stability.