Dual pivot quick is sorting algorithm based on quick sort. Its key idea is, instead of using 1 pivot in classic quick sort, it uses 2 pivot to split array into 3 parts. The overall time complexity is still the same, but in general, dual pivot quick sort executes faster then normal quick sort.

To understand dual pivot quick, you need to have a basic understanding of quick sort. If you don't, check my previous article about quick sort. Then, let's get started.

We know that in quick sort, we should use a pivot to split the array into 2 parts. All the values in left part is lower than the pivot value, all the values in the right part is larger than the pivot value. So we can continue to use the same process to these 2 subarrays. Code is like below.

function quickSort(nums: number[], low: number, high: number) {
    if (low > high) return;
    const mid = partition(nums, low, high);
    quickSort(nums, low, mid - 1);
    quickSort(nums, mid + 1, high);
}

In dual pivot quick sort, we use 2 pivot (pivot 1 and pivot 2) to split the array into 3 parts. Other process is the same. Code is similar too.

function dualPivotQuickSort(nums: number[], low: number, high: number) {
    if (low > high) return;
    const [p1, p2] = partition(nums, low, high);
    dualPivotQuickSort(nums, low, p1 - 1);
    dualPivotQuickSort(nums, p1 + 1, p2 - 1);
    dualPivotQuickSort(nums, p2 + 1, high);
}

In quick sort, to split array into 2 part, we select a pivot, use a for loop swap all values lower than pivot to the left, and all the values larger than the pivot will be in the right automatically. Code is like below.

function partition(nums: number[], low: number, high: number): number {
    let pivot = nums[high]; 
    let p = low; 
    for (let i = low; i < high; i++) {
        if (nums[i] <= pivot) {
            [nums[i], nums[p]] = [nums[p], nums[i]];
            p += 1;
        }
    }
    [nums[high], nums[p]] = [nums[p], nums[high]];
    return p;
}

The problem is how to split it into 3 parts in O(n) time complexity? Actually, this 3 part split problem is very similiar to the Dutch national flag problem, check my previous article about it.

The idea is, use 2 pointers, one from left, one from right. Move all the values lower than pivot 1 to the left, and move all the values larger than pivot 2 to the right. And the remaining values are between pivot 1 and pivot 2. Now let's see the code.

function swap(nums: number[], i: number, j: number) {
    [nums[i], nums[j]] = [nums[j], nums[i]];
}

function partition(nums: number[], low: number, high: number): [number, number] {
    if (nums[low] > nums[high]) {
        swap(nums, low, high);
    }

    let leftIndex = low + 1;
    let rightIndex = high - 1;

    let i = low + 1;

    while (i <= rightIndex) {
        if (nums[i] < nums[low]) {
            swap(nums, i++, leftIndex++);
        } else if (nums[i] >= nums[high]) {
            swap(nums, i, rightIndex--);
        } else {
            i += 1;
        }
    }

    swap(nums, low, --leftIndex);
    swap(nums, high, ++rightIndex);

    return [leftIndex, rightIndex];
}

OK, that's all of it. Don't forget to use the leetcode problem Sort an Array to test the code.

function sortArray(nums: number[]): number[] {
    dualPivotQuickSort(nums, 0, nums.length - 1);
    return nums;
};