Lecture_Notes/imperfect_notes/Sorting/2.md

Radix Sort

• sort elements from lowest significant to most significant values
• explain: basically counting sort on each bit / digit
• Stability: inherently stable - won't work if unstable
• complexity: O(n \log\max a[i])

Sex-Tuples

Given A[n], all distinct find the count of sex-tuples such that

\frac{a b + c}{d} - e = f

Note: numbers can repeat in the sextuple

• Naive: {n \choose 6} = O(n^6)
• Optimization. Rewrite the equation as ab + c = d(e + f)
  • Now, we only need {n \choose 3} = O(n^3)
  • Caution: d \neq 0
  • Once you have array of RHS, sort it in O(\log n^3) time.
  • Then for each value of LHS, count using binary search in the sorted array in \log n time.
  • Total: O(n^3 \log n)