Two-way quicksort

The two-way quicksort algorithm is an improved version of randomized quicksort. The partition process uses two index values (i, j) to traverse the array, placing<velements to the left of the position pointed to by index i, and placing>velements to the right of the position pointed to by index j,vRepresents the calibration value.

Applicability

The time and space complexity are the same as randomized quicksort. For arrays with many duplicate elements, using the randomized quicksort from the previous section is very inefficient, because the subarray lengths after partition for data greater than or less than the pivot become extremely unbalanced, and it may even degenerate into an algorithm withO(n*2)time complexity. For this situation, the two-way quicksort algorithm can be used.

Process Diagram

Use two index values (i, j) to traverse our sequence, placing<=velements to the left of the position pointed to by index i, and placing>=velements to the right of the position pointed to by index j, balancing the left and right subarrays.

Java example code

Source code package download:Download

QuickSort2Ways.java file code:

package example;

/**
* Two-Way Quick Sort
 */
public class QuickSort2Ways {

    // Core code --- start
    private static int partition(Comparable[] arr, int l, int r){
        // Randomly select a value as the pivot in the range arr[l...r]
        swap( arr, l , (int)(Math.random()*(r-l+1))+l );
        Comparable v = arr[l];
        // arr[l+1...i) <= v; arr(j...r] >= v
        int i = l+1, j = r;
        while( true ){
            while( i <= r && arr[i].compareTo(v) < 0 )
                i ++;
            while( j >= l+1 && arr[j].compareTo(v) > 0 )
                j --;
            if( i > j )
                break;
            swap( arr, i, j );
            i ++;
            j --;
        }
        swap(arr, l, j);
        return j;
    }
    // Core code --- end

    // Recursively use quicksort to sort the range arr[l...r]
    private static void sort(Comparable[] arr, int l, int r){
        if (l >= r) {
            return;
        }
        int p = partition(arr, l, r);
        sort(arr, l, p-1 );
        sort(arr, p+1, r);
    }

    public static void sort(Comparable[] arr){

        int n = arr.length;
        sort(arr, 0, n-1);
    }

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

    // Test QuickSort
    public static void main(String[] args) {

        // The Two-Way Quick Sort algorithm is also an O(nlogn) complexity algorithm
        // Can easily handle data on the order of 1 million within 1 second

        // Quick Sort is also an algorithm with O(n log n) complexity
        // Can easily handle data on the order of 1 million within 1 second
        int N = 1000000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        sort(arr);
        SortTestHelper.printArray(arr);

    }
}

Detailed explanation of the algorithm principle

The core of two-way quicksort lies in itsTwo-pointer partitioning methodUnlike one-way quicksort (which scans from only one end), it uses two pointers that scan from the head and tail of the subarray to be sorted toward the middle, ensuring that equal elements are not all pushed to one side.

Core: the two-way partitioning process

Suppose we want to sort the arrayarrmiddle index fromlefttorightportion.

Select pivot value: fromarr[left...right]Randomly select an element from it as the pivot valuepivotRandomization is used to avoid the worst case on sorted arrays.

Initialize pointers：

  • i = left + 1A pointer scanning from left to right, looking for the firstgreater than or equal to pivotelements.
  • j = rightA pointer scanning from right to left, looking for the firstless than or equal to pivotelements.

Scanning and swapping loop：

  • whileThe loop, with the condition beingi <= j。
  • innerwhileloop: letiKeep moving right untilarr[i] >= pivot。
  • innerwhileloop: letjKeep moving left untilarr[j] <= pivot。
  • At this point,arr[i]is a "large" element that should not be in the left half,arr[j]is a "small" element that should not be in the right half.
  • If at this pointi <= j, then swaparr[i]andarr[j], theni++, j--then continue the outer loop.

Place the pivot value and return the partition point：

  • After the loop ends,iandjalready crossed (j < i). At this pointarr[left](i.e., the pivot) needs to be placed in the correct position.
  • willarr[left]andarr[j]swap. BecausejThe position where it finally stops, and the element it points to isthe last element less than or equal to the pivot valueelements.
  • returnjas the new partition point. At this point,arr[left...j-1] <= pivot，arr[j+1...right] >= pivot, andarr[j] == pivot。

recursively sort

get the partition pointpAfter that, for the left subarrayarr[left...p-1]and the right subarrayarr[p+1...right]Repeat the above process recursively until the subarray length is 1.

Code implementation

Let us understand two-way quicksort concretely through a complete Java implementation.

1. Main sorting function

Example

public class TwoWayQuickSort {

    // Public sorting interface
    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return; // Handle boundary condition: array is empty or has only one element, no need to sort
        }
        quickSort(arr, 0, arr.length - 1); // Call the recursive quick sort function
    }

    // Recursive quick sort function
    private static void quickSort(int[] arr, int left, int right) {
        // Recursion termination condition: when left >= right, the subarray is already sorted or empty
        if (left >= right) {
            return;
        }
       
        // Key step: perform two-way partitioning and return the partition index
        int p = partition(arr, left, right);
       
        // Recursively sort the left half (left, p-1)
        quickSort(arr, left, p - 1);
        // Recursively sort the right half (p+1, right)
        quickSort(arr, p + 1, right);
    }
}

2. Core: two-way partitioning function

This is the core of the algorithm. Please understand it carefully together with the above flowchart and comments.

Example

    // Two-way partition function
    private static int partition(int[] arr, int left, int right) {
        // 1. Randomly select a pivot and swap it to the left position, avoiding the worst case on sorted arrays
        int randomIndex = left + (int)(Math.random() * (right - left + 1));
        swap(arr, left, randomIndex);
        int pivot = arr[left]; // Pivot value
       
        // 2. Initialize the two pointers
        // i: scan from left to right, looking for elements >= pivot
        // j: scan from right to left, looking for elements <= pivot
        int i = left + 1;
        int j = right;
       
        // 3. Main loop: while i and j haven't crossed
        while (i <= j) {
            // 3.1 Move left pointer i: find the first element >= pivot
            // Note boundary i <= right to prevent array out-of-bounds
            while (i <= right && arr[i] < pivot) {
                i++;
            }
            // 3.2 Move right pointer j: find the first element <= pivot
            // Note boundary j >= left+1, because the left position is the pivot itself
            while (j >= left + 1 && arr[j] > pivot) {
                j--;
            }
           
            // 3.3 Check pointer status
            // If i > j, scanning is complete, left and right partitions are ready, no need to swap
            if (i > j) {
                break;
            }
           
            // 3.4 Swap arr[i] and arr[j]
            // Now arr[i] >= pivot, arr[j] <= pivot, swap them so elements on both sides are in place
            swap(arr, i, j);
            // After swapping, move pointers to continue scanning
            i++;
            j--;
        }
       
        // 4. Place the pivot at its final correct position j
        // After the loop ends, j points to the last element <= pivot
        swap(arr, left, j);
       
        // 5. Return the index j of the partition point
        return j;
    }
   
    // Helper function: swap the positions of two elements in an array
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

3. Testing and verification

Let us test our implementation with an array containing duplicate elements.

Example

public class Main {
    public static void main(String[] args) {
        // Test case 1: array containing many duplicate elements
        int[] arr1 = {4, 2, 2, 8, 3, 3, 1, 5, 3, 2};
        System.out.println("Before sorting: " + Arrays.toString(arr1));
        TwoWayQuickSort.sort(arr1);
        System.out.println("After sorting: " + Arrays.toString(arr1));
       
        // Test case 2: large randomly generated array
        int[] arr2 = new int[20];
        Random rand = new Random();
        for (int i = 0; i < arr2.length; i++) {
            arr2[i] = rand.nextInt(50); // Generate random numbers from 0-49, duplicates likely
        }
        System.out.println("\n"Before sorting random array: " + Arrays.toString(arr2));
        TwoWayQuickSort.sort(arr2);
        System.out.println("After sorting random array: " + Arrays.toString(arr2));
       
        // Verify whether the sorting result is correct
        for (int i = 1; i < arr2.length; i++) {
            if (arr2[i] < arr2[i-1]) {
                System.out.println("Sorting error!");
                return;
            }
        }
        System.out.println("Sorting result verification passed!");
    }
}

Test data output example：

排序前: [4, 2, 2, 8, 3, 3, 1, 5, 3, 2]
排序后: [1, 2, 2, 2, 3, 3, 3, 4, 5, 8]

随机数组排序前: [17, 33, 12, 48, 8, 2, 41, ...]
随机数组排序后: [2, 8, 12, 17, 33, 33, 41, 48, ...]
排序结果验证通过！

Algorithm analysis and comparison

Time complexity

  • Average case:$O(n \log n)$. Two-way quicksort keeps the recursion tree relatively balanced by evenly distributing duplicate elements.
  • Worst case:$O(n^2)$. Although randomized pivot selection greatly reduces the probability, the worst case can still occur when every partition is extremely unbalanced (for example, when the pivot is always the current minimum or maximum value).
  • Best case:$O(n \log n)$. Each partition divides the array evenly.

Space complexity

  • It is mainly the space occupied by the recursive call stack.
  • The average depth is $O(\log n)$, and the worst-case depth is $O(n)$.
  • Therefore,The average space complexity is $O(\log n)$, and the worst case is $O(n)$.。

Stability

Quicksort (including two-way quicksort) is not a stable sorting algorithm, because during partitioning, swaps of non-adjacent elements can disrupt the original relative order of equal elements.

Comparison of one-way, two-way, and three-way quicksort

Features One-way quicksort (Lomuto) Two-way quicksort Three-way quicksort
Partition method Single pointer scans from left to right Two pointers scan from both ends toward the middle Three pointers, dividing the array into<pivot, =pivot, >pivotThree parts
Handling duplicate elements Poor, may lead to unbalanced partitioning Good, can evenly distribute duplicate elements Optimal, can handle all elements equal to the pivot at once
Code complexity Simple Medium Slightly complex
Applicable scenarios Teaching, no/few duplicate elements General-purpose, especially suitable for scenarios where duplicate elements may exist Scenarios with a large number of duplicate elements

More code examples

other extensions