Sort an array with many repeated entries (3-way quicksort)

Medium

Problem

Sort an array that has many duplicate values efficiently. Plain quicksort degrades to O(n²) on many equal keys. Partition into less than, equal to and greater than the pivot instead.

Example 1

Input:  [4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4]
Output: [1, 1, 4, 4, 4, 4, 4, 4, 4, 4, 9, 9, 9]

Also asked as: Partitioning and Sorting Arrays with Many Repeated Entries

Test cases

Case 1

Input:    [4,9,4,4,1,9,4,4,9,4,4,1,4]
Expected: [1,1,4,4,4,4,4,4,4,4,9,9,9]

Case 2

Input:    [3,3,3]
Expected: [3,3,3]

Case 3

Input:    [2,1]
Expected: [1,2]

Case 4

Input:    []
Expected: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. 3-way (Dutch flag) quicksort

Time O(n log n), O(n·k) for k distinct keysSpace O(log n)

Partition into < pivot, === pivot, > pivot. The equal band is skipped entirely, so duplicates cost nothing — O(n) when few distinct keys.

function quicksort3(a, lo = 0, hi = a.length - 1) {
if (lo >= hi) return a;
const pivot = a[(lo + hi) >> 1];
let lt = lo, gt = hi, i = lo;
while (i <= gt) {
if (a[i] < pivot) [a[lt++], a[i++]] = [a[i], a[lt]];
else if (a[i] > pivot) [a[i], a[gt--]] = [a[gt], a[i]];
else i++;
}
quicksort3(a, lo, lt - 1);
quicksort3(a, gt + 1, hi);
return a;
}