Let $T(n)$ denote the time taken to sort a list of n records. Which of the following statements are false for QuickSort?