Please critique my implementation of Quicksort in python 3.8:
import random from typing import List def quicksort(A: List[int], left: int, right: int): """ Sort the array in-place in the range [left, right( """ if left >= right: return pivot_index = random.randint(left, right - 1) swap(A, left, pivot_index) pivot_new_index = partition(A, left, right) quicksort(A, left, pivot_new_index) quicksort(A, pivot_new_index + 1, right) def partition(A: List[int], left: int, right: int) -> int: """ in-place partition around first item """ if left >= right: return left pivot = A[left] # initialize i, j pointers j = left + 1 while j < right and A[j] <= pivot: j += 1 i = j # invariant : # A[left+1 ... i-1] <= pivot # A[i ... j-1] > pivot # A[j ... right( unexplored while j < right: if A[j] <= pivot: swap(A, i, j) i += 1 j += 1 swap(A, left, i - 1) return i - 1 def swap(A: List[int], i: int, j: int): A[i], A[j] = A[j], A[i]
I followed Tim Roughgarden's explanations in his MOOC on algorithms. But he assumes the keys are all distinct and says that having Quicksort work efficiently on many duplicated keys is trickier than it seems and point to Robert Sedgewick and Kevin Wayne book on algorithms. I checked it and the partition method looks indeed way different.
My current code seems to work even with duplicated keys but I think if all the keys are the same, I will get a O(n²) complexity (partitioned arrays will be very unbalanced). How can I update my current code to address this issue?