Hybrid Quick Sort - DNF Partitioning

QuickSort with Dutch National Flag 3-way partitioning and random pivot selection

Array

Pivot

Random selected

Low

Next pos for < pivot

Mid

Current element

High

Next pos for > pivot

Call Stack (Pending Ranges)

Stack empty

Current Range: -

Click "Step" or "Play" to start the visualization

Pivot

< Pivot

= Pivot

> Pivot

Sorted

Out of Range

▲ low - boundary for < pivot

▼ mid - current scan

▲ high - boundary for > pivot

Python Code - Hybrid Quick Sort (DNF)

                def _partition(nums, l, h):
            
                    pivot = nums[random.randint(l, h)]
            
                    low, mid, high = l, l, h
            
                    while mid <= high:
            
                        if nums[mid] < pivot:
            
                            swap(nums[low], nums[mid])
            
                            low += 1; mid += 1
            
                        elif nums[mid] == pivot:
            
                            mid += 1
            
                        else: # nums[mid] > pivot
            
                            swap(nums[mid], nums[high])
            
                            high -= 1
            
                    return low, high
            
                def _quickSort(nums, l, h):
            
                    if not l < h: return
            
                    low, high = _partition(nums, l, h)
            
                    _quickSort(nums, l, low - 1)
            
                    _quickSort(nums, high + 1, h)

Complexity Analysis

Time Complexity O(n log n) avg Space Complexity O(log n)

Time Complexity: O(n log n) average

Breakdown

Partition: O(n) — single pass through subarray
Recursion depth: O(log n) expected with random pivot
Total work per level: O(n)
Worst case: O(n²) when pivot is always min/max

T(n) = 2T(n/2) + O(n) → O(n log n) by Master theorem

Mathematical Intuition

Random pivot selection ensures that with high probability, each partition divides the array into reasonably balanced parts. Three-way partitioning handles duplicates by grouping equal elements together—excluded from recursion. For arrays with k distinct values, runtime approaches O(n log k).

Key Insight

The DNF partition transforms the O(n²) duplicate-heavy worst case into O(n) by processing all equal elements in one partition step.

Space Complexity: O(log n)

Breakdown

Recursion stack depth: O(log n) average
Each stack frame: O(1) local variables
In-place partitioning: no auxiliary arrays
Worst case: O(n) with pathological pivots

S(n) = O(log n) — recursion stack only

Mathematical Intuition

Unlike merge sort (O(n) auxiliary space), quicksort partitions in-place. Space is dominated by the call stack. Tail-call optimization on the larger partition can guarantee O(log n) stack depth even in the worst case.

Key Insight

Introsort (used in std::sort) switches to heapsort when recursion exceeds 2⌊log n⌋, guaranteeing O(n log n) worst-case while preserving quicksort's cache efficiency.