1. Introduction

Quicksort is one of the fastest and most widely used sorting algorithms due to its efficiency and in-place sorting behavior. Traditionally, Quicksort uses one pivot to partition an array into two parts:

• elements smaller than the pivot, and
• elements greater than the pivot.

However, in Dual-Pivot Quicksort, the idea is extended to use two pivots instead of one. This allows partitioning the array into three parts in a single pass, leading to potentially better performance.

Dual-Pivot Quicksort was introduced by Vladimir Yaroslavskiy and adopted in Java 7’s Arrays.sort() for primitive types because it offered significant performance improvements in real-world data compared to the classic single-pivot Quicksort.

---

2. Intuition Behind Dual-Pivot Quicksort

Suppose we choose two pivots, pivot1 and pivot2, such that pivot1 <= pivot2.
The array is then divided into three segments:

1. Elements less than pivot1
2. Elements between pivot1 and pivot2
3. Elements greater than pivot2

This structure helps reduce the recursion depth and number of comparisons since more work is done in each partitioning step.

For example, consider the array:

[9, 3, 7, 1, 8, 12, 2, 10]

If we choose:

pivot1 = 3, pivot2 = 8

Then after partitioning:

[1, 2] [3, 7] [9, 12, 10]

Now, recursive sorting is applied only to these three smaller sections.

---

3. Steps of the Algorithm

1. Choose Two Pivots
   Select the first and last elements as pivots (or use a randomization strategy for better average performance).
   Ensure pivot1 < pivot2. If not, swap them.
2. Partition the Array
   Rearrange the array so that:
   • Elements < pivot1 go to the left,
   • Elements >= pivot1 and <= pivot2 go to the middle,
   • Elements > pivot2 go to the right.
3. Recursive Sorting
   Recursively sort the three partitions:
   • Left part (less than pivot1)
   • Middle part (between pivot1 and pivot2)
   • Right part (greater than pivot2)
4. Combine Results
   Since sorting happens in-place, after recursion, the array becomes sorted.

---

4. Pseudocode

dualPivotQuickSort(arr, low, high):
    if low < high:
        // step 1: choose two pivots
        pivot1 = arr[low]
        pivot2 = arr[high]
        
        if pivot1 > pivot2:
            swap(pivot1, pivot2)
            arr[low], arr[high] = pivot1, pivot2

        // step 2: partitioning
        lt = low + 1        // pointer for < pivot1
        gt = high - 1       // pointer for > pivot2
        i = lt

        while i <= gt:
            if arr[i] < pivot1:
                swap(arr[i], arr[lt])
                lt += 1
            else if arr[i] > pivot2:
                swap(arr[i], arr[gt])
                gt -= 1
                i -= 1       // recheck swapped element
            i += 1

        lt -= 1
        gt += 1
        swap(arr[low], arr[lt])      // place pivot1
        swap(arr[high], arr[gt])     // place pivot2

        // step 3: recursive calls
        dualPivotQuickSort(arr, low, lt - 1)
        dualPivotQuickSort(arr, lt + 1, gt - 1)
        dualPivotQuickSort(arr, gt + 1, high)

---

5. Java Implementation

public class DualPivotQuickSort {

    public static void dualPivotQuickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Choose pivots
            if (arr[low] > arr[high]) {
                swap(arr, low, high);
            }
            int pivot1 = arr[low];
            int pivot2 = arr[high];

            int lt = low + 1;
            int gt = high - 1;
            int i = lt;

            while (i <= gt) {
                if (arr[i] < pivot1) {
                    swap(arr, i, lt);
                    lt++;
                } else if (arr[i] > pivot2) {
                    swap(arr, i, gt);
                    gt--;
                    i--; // re-evaluate swapped value
                }
                i++;
            }

            lt--;
            gt++;
            swap(arr, low, lt);
            swap(arr, high, gt);

            // Recursive calls
            dualPivotQuickSort(arr, low, lt - 1);
            dualPivotQuickSort(arr, lt + 1, gt - 1);
            dualPivotQuickSort(arr, gt + 1, high);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {24, 8, 42, 75, 29, 77, 38, 57};
        dualPivotQuickSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array:");
        for (int n : arr) {
            System.out.print(n + " ");
        }
    }
}

Output:

Sorted array:
8 24 29 38 42 57 75 77

---

6. Dry Run Example

Input Array: [9, 3, 7, 1, 8, 12, 2, 10]
low = 0, high = 7

Step 1: Choose pivots

pivot1 = 9
pivot2 = 10

Since 9 < 10, no swap needed.

Step 2: Partitioning

Initial pointers:
lt = 1, gt = 6, i = 1

i	arr[i]	Action	Array after swap
1	3	< pivot1 → swap(arr[i], arr[lt])	[9,3,7,1,8,12,2,10]
2	7	< pivot1 → swap(arr[i], arr[lt])	[9,3,7,1,8,12,2,10]
3	1	< pivot1 → swap(arr[i], arr[lt])	[9,3,7,1,8,12,2,10]
4	8	< pivot1 → swap(arr[i], arr[lt])	[9,3,7,1,8,12,2,10]
5	12	> pivot2 → swap(arr[i], arr[gt])	[9,3,7,1,8,2,12,10], gt=5
5	2	< pivot1 → swap(arr[i], arr[lt])	[9,3,7,1,8,2,12,10]

After loop:

lt = 5, gt = 6
swap(arr[0], arr[lt-1]) → swap(9,8)
swap(arr[7], arr[gt+1]) → swap(10,12)

Array becomes roughly partitioned, and recursion proceeds on three smaller parts.

---

7. Time and Space Complexity

Case	Time Complexity	Explanation
Best Case	O(n log n)	Array divided into nearly equal thirds in each recursive call
Average Case	O(n log n)	Balanced partitions on random data
Worst Case	O(n²)	Happens when pivots are chosen poorly (all elements equal or nearly sorted)
Space Complexity	O(log n)	Due to recursion stack (in-place sorting)

In practice, Dual-Pivot Quicksort is faster than classic Quicksort because it reduces the number of swaps and comparisons per element.

---

8. Advantages

1. Fewer Comparisons: Two pivots help reduce the total number of element comparisons.
2. Reduced Recursion Depth: The array gets divided into three parts instead of two.
3. Improved Cache Efficiency: Works well with modern CPU cache lines.
4. Practical Performance: Java 7 and above use Dual-Pivot Quicksort for primitive arrays because it consistently performs better on real-world data.

---

9. Disadvantages

1. More Complex Implementation: Logic for two pivots is more difficult to code and maintain.
2. Extra Overhead for Small Arrays: For very small arrays, insertion sort may perform better.
3. Sensitive to Pivot Choice: Poor pivot selection can degrade performance to O(n²).

---

10. Comparison with Classic Quicksort

Feature	Single Pivot	Dual Pivot
Number of Pivots	1	2
Partitions per Step	2	3
Comparisons	More	Fewer
Recursion Depth	Higher	Lower
Implementation	Simple	Complex
Java Implementation	Used before Java 7	Default since Java 7 for primitives

---

11. Conclusion

Dual-Pivot Quicksort is a powerful variant of Quicksort that improves real-world performance by partitioning the array into three segments at once. While its theoretical complexity remains O(n log n), its practical efficiency, better cache utilization, and fewer comparisons make it a preferred choice in modern Java implementations.