Animated Sorting Algorithm Demo: 3-Way Partition Quick Sort

Algorithm

# choose pivot
i = rand(1,n)
swap a[i,n]

# 3-way partition
k = 1, p = n
while i < p,
  if a[i] < a[n], swap a[i++,k++]
  else if a[i] == a[n], swap a[i,--p]
  else i++
end
m = min(p-k,n-p+1)
swap a[k..k+m-1,n-m+1..n]

# recursive sorts
sort a[1..k-1]
sort a[n-p+k+1,n]
        

Properties

• Not stable
• In place
• Worst case O(n) extra space for recursion stack
• Best case Ω(lg(n)) extra space for recursion stack
• Worst case O(n²) time
• Typically O(n·lg(n)) time
• Adaptive: O(n) when O(1) unique keys

Discussion

The 3-way partition variation of quicksort has slightly higher overhead compared to the standard 2-way parition version. Both have the same best, typical, and worst case time bounds, but this version does not exhibit quadratic behavior in the common case of sorting with few unique keys. The benefit of avoiding quadratic time more than offsets the minor increase in overhead.

Directions

• Click on to restart the animations.
• Click on a size number to change the size of the examples.
• Click on a cell to restart an individual animation.
• Click on a cell title to explore that input order.

Key

• Black values are sorted.
• Gray values are unsorted.
• Dark gray values show the current sub-array that is being sorted recursively.
• A pair of red triangles mark k and p (see the code).

References

Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.

Programming Pearls by Jon Bentley. Addison Wesley, 1986.