Sort an array with many repeated entries (3-way quicksort)
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: []
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;}