QuickSort (Optimized with Median-of-Three Pivot) - CSU083 | Shoolini University

QuickSort (Optimized with Median-of-Three Pivot)

2025, February 21

1. Prerequisites

Understanding QuickSort with the median-of-three pivot requires foundational knowledge in:

2. What is QuickSort (Optimized with Median-of-Three Pivot)?

QuickSort is an efficient, in-place sorting algorithm that works by:

  1. Choosing a pivot element.
  2. Partitioning the array such that elements smaller than the pivot go to the left and larger ones go to the right.
  3. Recursively sorting the left and right partitions.

The median-of-three pivot selection optimizes QuickSort by choosing the pivot as the median of the first, middle, and last elements of the array. This minimizes worst-case scenarios, such as when the array is already sorted or nearly sorted.

3. Why Does This Algorithm Exist?

QuickSort is widely used because of its efficiency and adaptability:

4. When Should You Use It?

QuickSort with median-of-three pivot is best used when:

5. How Does It Compare to Alternatives?

5.1 Strengths

5.2 Weaknesses

5.3 Comparison with Other Sorting Algorithms

Algorithm Time Complexity (Avg) Space Complexity Stable? Best Use Case
QuickSort (Median-of-Three) O(n log n) O(log n) No Large datasets, in-place sorting
MergeSort O(n log n) O(n) Yes Linked lists, stable sorting required
HeapSort O(n log n) O(1) No Priority queues, real-time applications
Insertion Sort O(n²) O(1) Yes Small datasets, nearly sorted data

6. Basic Implementation

6.1 Python Implementation

Here is the Python implementation of QuickSort using the median-of-three pivot selection:


def median_of_three(arr, low, high):
    mid = (low + high) // 2
    a, b, c = arr[low], arr[mid], arr[high]
    
    if a > b:
        if a < c:
            return low
        elif b > c:
            return mid
        else:
            return high
    else:
        if a > c:
            return low
        elif b < c:
            return mid
        else:
            return high

def partition(arr, low, high):
    pivot_index = median_of_three(arr, low, high)
    arr[pivot_index], arr[high] = arr[high], arr[pivot_index]  # Move pivot to end
    pivot = arr[high]
    
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]  # Swap elements
            
    arr[i + 1], arr[high] = arr[high], arr[i + 1]  # Place pivot correctly
    return i + 1

def quicksort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quicksort(arr, low, pi - 1)
        quicksort(arr, pi + 1, high)

# Example Usage
arr = [29, 10, 14, 37, 13]
quicksort(arr, 0, len(arr) - 1)
print("Sorted Array:", arr)

7. Dry Run of QuickSort (Median-of-Three Pivot)

7.1 Given Input Array:

[29, 10, 14, 37, 13]

7.2 Step-by-Step Execution:

Step Action Array State Pivot
1 Choose pivot using median-of-three (low=29, mid=14, high=13) → Median is 14 [29, 10, 13, 37, 14] 14
2 Partition: Move elements & place pivot correctly [10, 13, 14, 37, 29] 14
3 Recursive call on left subarray [10, 13] [10, 13, 14, 37, 29] 13
4 Partition left subarray [10, 13, 14, 37, 29] 13
5 Recursive call on right subarray [37, 29] [10, 13, 14, 37, 29] 37
6 Partition right subarray [10, 13, 14, 29, 37] 29
7 Final sorted array [10, 13, 14, 29, 37] -

8. Time & Space Complexity Analysis

8.1 Time Complexity

QuickSort's efficiency is determined by how well the partitioning step divides the array. The median-of-three pivot selection improves performance by reducing the likelihood of unbalanced partitions.

The recurrence relation for balanced partitions is:

$$ T(n) = 2T(n/2) + O(n) $$

Solving using Master Theorem:

$$ T(n) = O(n \log n) $$

9. Space Complexity Analysis

QuickSort is an in-place sorting algorithm, meaning it does not require extra space beyond the input array (except for recursion stack memory).

10. Trade-offs of QuickSort (Median-of-Three)

10.1 Advantages

10.2 Disadvantages

10.3 When to Use & When to Avoid

When to Use When to Avoid
Sorting large datasets efficiently When stability (preserving equal elements' order) is required
In-place sorting is needed When recursion overhead is a concern (e.g., small embedded systems)
Handling nearly sorted data with optimization If worst-case O(n²) must be strictly avoided (use HeapSort/MergeSort)

11. Optimizations & Variants (Making It Efficient)

11.1 Common Optimizations

11.2 Variants of QuickSort

11.2.1 Three-Way QuickSort (Dutch National Flag Algorithm)

Divides the array into three parts: elements smaller than pivot, equal to pivot, and greater than pivot. Useful when dealing with many duplicate values.

11.2.2 Hybrid QuickSort

Combines QuickSort with Insertion Sort or MergeSort for better performance in different scenarios.

11.2.3 Dual-Pivot QuickSort

Instead of using a single pivot, it selects two pivots to create three partitions, improving efficiency.

12. Comparing Iterative vs. Recursive Implementations

12.1 Recursive QuickSort

The traditional implementation of QuickSort is recursive:

12.2 Iterative QuickSort

Uses an explicit stack instead of function calls:


def iterative_quicksort(arr):
    stack = [(0, len(arr) - 1)]

    while stack:
        low, high = stack.pop()
        if low < high:
            pivot = partition(arr, low, high)
            stack.append((low, pivot - 1))
            stack.append((pivot + 1, high))

# Uses same partition function as recursive QuickSort

12.3 Which One is Better?

Aspect Recursive QuickSort Iterative QuickSort
Ease of Implementation Simple More complex
Memory Usage O(log n) (best), O(n) (worst) O(log n) (always)
Performance Efficient but may hit recursion limits More stable memory usage
Suitability for Large Inputs Risk of stack overflow Better suited

Conclusion: Recursive QuickSort is easier to implement and works well for most cases, but Iterative QuickSort is preferred for handling large datasets where recursion depth is a concern.

13. Edge Cases & Failure Handling

13.1 Common Pitfalls and Edge Cases

14. Test Cases for Verifying Correctness

14.1 Basic Test Cases


def test_quicksort():
    test_cases = [
        ([3, 1, 4, 1, 5, 9, 2, 6], [1, 1, 2, 3, 4, 5, 6, 9]),  # Random order
        ([5, 4, 3, 2, 1], [1, 2, 3, 4, 5]),  # Reverse sorted
        ([1, 2, 3, 4, 5], [1, 2, 3, 4, 5]),  # Already sorted
        ([10], [10]),  # Single element
        ([], []),  # Empty array
        ([7, 7, 7, 7], [7, 7, 7, 7]),  # All elements identical
    ]
    
    for i, (arr, expected) in enumerate(test_cases):
        quicksort(arr, 0, len(arr) - 1)
        assert arr == expected, f"Test case {i + 1} failed"
    print("All test cases passed!")

# Run the test
test_quicksort()

15. Real-World Failure Scenarios

15.1 Sorting Large Datasets

For very large datasets, QuickSort may hit recursion depth limits. Solution: Use iterative QuickSort or Hybrid QuickSort with MergeSort.

15.2 Unstable Sorting

If stable sorting is needed (e.g., maintaining relative order of equal elements in database records), MergeSort should be used instead.

15.3 Security Concerns: QuickSort DoS Attack

In security-sensitive applications, attackers can craft input that triggers worst-case O(n²) performance. Solution: Implement randomized QuickSort or use introspective sorting (Introsort) that switches to HeapSort when recursion depth exceeds a threshold.

16. Real-World Applications & Industry Use Cases

16.1 Where QuickSort (Median-of-Three) is Used

QuickSort with the median-of-three pivot is widely used in performance-critical applications due to its efficiency in average-case sorting.

17. Open-Source Implementations

17.1 QuickSort Implementations in Open-Source Projects

Several popular open-source projects use QuickSort in their sorting implementations:

17.2 Open-Source Code Repositories

For reference, here are some open-source QuickSort implementations:

18. Practical Project: Sorting Large Log Files

18.1 Project Overview

We will build a Python script to sort large log files using QuickSort (Median-of-Three). This is useful in system monitoring and security analysis.

18.2 Code Implementation


import os

# QuickSort with Median-of-Three Pivot
def median_of_three(arr, low, high):
    mid = (low + high) // 2
    a, b, c = arr[low], arr[mid], arr[high]
    
    if a > b:
        if a < c:
            return low
        elif b > c:
            return mid
        else:
            return high
    else:
        if a > c:
            return low
        elif b < c:
            return mid
        else:
            return high

def partition(arr, low, high):
    pivot_index = median_of_three(arr, low, high)
    arr[pivot_index], arr[high] = arr[high], arr[pivot_index]
    pivot = arr[high]
    
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quicksort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quicksort(arr, low, pi - 1)
        quicksort(arr, pi + 1, high)

# Function to read and sort log files
def sort_log_file(input_file, output_file):
    with open(input_file, 'r') as f:
        log_entries = f.readlines()
    
    log_entries = [line.strip() for line in log_entries]
    
    quicksort(log_entries, 0, len(log_entries) - 1)
    
    with open(output_file, 'w') as f:
        for line in log_entries:
            f.write(line + "\n")

# Example Usage
log_file = "system_logs.txt"
sorted_log_file = "sorted_logs.txt"

if os.path.exists(log_file):
    sort_log_file(log_file, sorted_log_file)
    print(f"Log file sorted and saved to {sorted_log_file}")
else:
    print(f"File {log_file} not found.")

18.3 Explanation

18.4 Real-World Use Case

Security professionals and system administrators can use this script to sort logs before searching for anomalies, making forensic analysis more efficient.

19. Competitive Programming & System Design Integration

19.1 QuickSort in Competitive Programming

QuickSort (Median-of-Three) is frequently used in programming contests due to its efficiency and in-place sorting capability.

19.2 QuickSort in System Design

In real-world systems, QuickSort (Median-of-Three) is used where fast, in-place sorting is required.

20. Assignments & Practice Problems

20.1 Solve At Least 10 Problems Using QuickSort

Practice QuickSort by solving the following problems:

  1. Basic QuickSort Implementation
  2. Leetcode: Sort an Array
  3. CodeChef: QuickSort Analysis
  4. HackerRank: QuickSort Part 1
  5. Recursive vs Iterative QuickSort
  6. Leetcode: K Closest Points to Origin (Sorting-based solution)
  7. QuickSort on Linked List
  8. Leetcode: Merge Intervals (Sorting-based problem)
  9. Sort Elements by Frequency
  10. HackerRank: Closest Numbers

20.2 System Design Assignment

Design a sorting-based component for a real-world system:

20.3 Implementing QuickSort Under Time Constraints

Time yourself and implement QuickSort (Median-of-Three) within 15 minutes:

20.4 Bonus Challenge

Modify QuickSort to be fully parallelized and execute on multi-core systems using Python’s multiprocessing library.