Stability Analysis and Optimization of Quick Sort

Problem Description
The stability of Quick Sort is an important interview topic. Stability refers to whether a sorting algorithm can preserve the original relative order of equal elements. We will delve into the reasons why Quick Sort is unstable, explore how to implement a stable version, and discuss related optimization strategies.

Basic Concepts

1. Definition of Stability: A sorting algorithm is stable if it preserves the original relative order of elements with equal keys.
2. Standard Quick Sort is typically unstable because the partition process may change the relative positions of equal elements.

Instability Analysis
The instability of standard Quick Sort mainly originates from the partition process:

def partition(arr, low, high):
    pivot = arr[high]  # Choose the last element as the pivot
    i = low - 1
    
    for j in range(low, high):
        if arr[j] <= pivot:  # Note the "<=" relation
            i += 1
            arr[i], arr[j] = arr[j], arr[i]  # Swapping may break stability
    
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i+1

Instability Example
Consider the array: [3a, 2, 3b, 1] (where 3a and 3b represent different elements with equal value)

• Choose the last element 1 as the pivot
• After partition, the relative positions of 3a and 3b may change

Methods for Implementing Stable Quick Sort

Method 1: Extra Space Approach

def stable_quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr)//2]  # Choose the middle element as the pivot
    
    # Use extra space to store three sub-arrays
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]  # Preserve the order of equal elements
    right = [x for x in arr if x > pivot]
    
    return stable_quick_sort(left) + middle + stable_quick_sort(right)

Method 2: Index Tracking Approach

def stable_quick_sort_inplace(arr):
    def sort_with_indices(indices):
        if len(indices) <= 1:
            return indices
        
        pivot_idx = indices[len(indices)//2]
        pivot_val = arr[pivot_idx]
        
        left, middle, right = [], [], []
        
        for idx in indices:
            if arr[idx] < pivot_val:
                left.append(idx)
            elif arr[idx] == pivot_val:
                # Preserve the original index order
                if idx <= pivot_idx:
                    middle.insert(0, idx)  # Maintain stability among equal elements
                else:
                    middle.append(idx)
            else:
                right.append(idx)
        
        return sort_with_indices(left) + middle + sort_with_indices(right)
    
    sorted_indices = sort_with_indices(list(range(len(arr))))
    return [arr[i] for i in sorted_indices]

Stability Optimization Strategies

Strategy 1: Three-Way Partition (Dutch National Flag)

def three_way_quicksort(arr, low, high):
    if low >= high:
        return
    
    # Three-way partition: Divide the array into <pivot, ==pivot, >pivot parts
    lt, i, gt = low, low, high
    pivot = arr[low]  # Choose the first element as the pivot
    
    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1
        else:
            i += 1
    
    # Recursively process the left and right parts
    three_way_quicksort(arr, low, lt-1)
    three_way_quicksort(arr, gt+1, high)

Strategy 2: Stable Partition Algorithm

def stable_partition(arr, low, high):
    """Implement a stable partition operation"""
    pivot = arr[high]
    n = high - low + 1
    temp = [0] * n
    
    # First pass: Collect elements less than the pivot
    left = 0
    for i in range(low, high+1):
        if arr[i] < pivot:
            temp[left] = arr[i]
            left += 1
    
    # Second pass: Collect elements equal to the pivot (preserving order)
    equal_start = left
    for i in range(low, high+1):
        if arr[i] == pivot:
            temp[left] = arr[i]
            left += 1
    
    # Third pass: Collect elements greater than the pivot
    right_start = left
    for i in range(low, high+1):
        if arr[i] > pivot:
            temp[left] = arr[i]
            left += 1
    
    # Copy back to the original array
    for i in range(n):
        arr[low + i] = temp[i]
    
    return equal_start, right_start - 1

Performance Analysis

Time Complexity Comparison

• Standard Quick Sort: Average O(n log n), Worst O(n²)
• Stable Quick Sort: Average O(n log n), but with a larger constant factor
• Space Complexity: Standard version O(log n), Stable version O(n)

Application Scenario Analysis

1. When stability is required: Use the stable version or three-way partition.
2. Memory-sensitive situations: Use the standard unstable version.
3. Large number of duplicate elements: Three-way partition is more efficient.

Interview Key Points Summary

1. Understand the root cause of instability: Element swapping during the partition process.
2. Master methods for achieving stability: Extra space approach, index tracking approach.
3. Understand optimization strategies: Three-way partition, stable partition.
4. Able to analyze the time/space complexity trade-off.
5. Choose the appropriate variant based on specific scenarios.