no of times partion is called in quick sort, assuming array is always halved

Question

In the most even possible split, PARTITION function produces two subarrays, each of size no more than n/2. since one is of size floor(n/2) and one of size ceil(n/2)-1.
The recurrence for the running time will be,

$$ T(n) = 2T(n/2) + \Theta(n) $$

where we tolerate the sloppiness from ignoring the floor and ceiling and from subtracting 1. By case 2 of the master theorem, this recurrence will have the solution $$ T(n) = \Theta(n \log n) $$ My Implementation is as follows:

QUICKSORT(A, p, r)
  if p < r
  q = PARTITION(A, p, r)
  QUICKSORT(A, p, q-1)
  QUICKSORT(A, q+1, r)

PARTITION(A, p, r)
  x = A[r]
  i = p - 1
  for j = p to (r - 1)
      if A[j] <= x
          i = i + 1
          exchange A[i] with A[j] 
  exchange A[i+1] with A[r]
  return i + 1

Assuming that the array is always divided into 2 equal halves, how many times is the partition algorithm will be called?

Answer 1

The number of times the partition algorithm is called does not actually depend on where the array is partitioned (asymptotically).

To count the number of partitions you just need to count the number of internal nodes in the recursion tree. Since each internal node has at least two children, the recursion tree is a full binary tree. In a full binary tree, the number of leaves and internal nodes are linearly related (see this link). So the number of internal nodes would be $\Theta(n)$, no matter where the partition happens. You can easily prove this using induction on the number of nodes in the tree.

Answer 2

If you use a partition algorithm that divides a range of numbers into a left and a right half, then you can look at every partition call as inserting one separator between two subranges into the array. And quicksort ends when there is a separator between any two array elements.

Therefore sorting an array of n >= 1 elements takes exactly n-1 calls to the partition function. This is totally independent of the choice of pivot and the execution time.

You will have fewer calls when the partition algorithm can create a left half, right half, and possibly k equal items in the middle; this would save k partition calls whenever k >= 1. You will also have fewer calls if small subranges are sorted using bubble sort, insertion sort or whatever is fastest for very small arrays.