PARTITION(A, 1, 9) on [7 2 9 4 1 8 3 6 5], pivot x = A[9] = 5
    j=1  A[j]= 7  >  x: no change             [7 2 9 4 1 8 3 6 5]
    j=2  A[j]= 2  <= x: i=1, swap A[i],A[j]   [2 7 9 4 1 8 3 6 5]
    j=3  A[j]= 9  >  x: no change             [2 7 9 4 1 8 3 6 5]
    j=4  A[j]= 4  <= x: i=2, swap A[i],A[j]   [2 4 9 7 1 8 3 6 5]
    j=5  A[j]= 1  <= x: i=3, swap A[i],A[j]   [2 4 1 7 9 8 3 6 5]
    j=6  A[j]= 8  >  x: no change             [2 4 1 7 9 8 3 6 5]
    j=7  A[j]= 3  <= x: i=4, swap A[i],A[j]   [2 4 1 3 9 8 7 6 5]
    j=8  A[j]= 6  >  x: no change             [2 4 1 3 9 8 7 6 5]
    final swap A[5] <-> A[9]                  [2 4 1 3 5 8 7 6 9]   q = 5

The whole QUICKSORT on the same array
QUICKSORT(A,1,9)  pivot 5 lands at q=5  (8 comparisons)  [2 4 1 3 5 8 7 6 9]
  QUICKSORT(A,1,4)  pivot 3 lands at q=3  (3 comparisons)  [2 1 3 4]
    QUICKSORT(A,1,2)  pivot 1 lands at q=1  (1 comparison)  [1 2]
  QUICKSORT(A,6,9)  pivot 9 lands at q=9  (3 comparisons)  [8 7 6 9]
    QUICKSORT(A,6,8)  pivot 6 lands at q=6  (2 comparisons)  [6 7 8]
      QUICKSORT(A,7,8)  pivot 8 lands at q=8  (1 comparison)  [7 8]
sorted: [1 2 3 4 5 6 7 8 9]   total comparisons = 18, deepest level = 3

Check yourself: PARTITION on [3 8 1 6 2 7 5 4], pivot 4
    j=1  A[j]= 3  <= x: i=1, swap A[i],A[j]   [3 8 1 6 2 7 5 4]
    j=2  A[j]= 8  >  x: no change             [3 8 1 6 2 7 5 4]
    j=3  A[j]= 1  <= x: i=2, swap A[i],A[j]   [3 1 8 6 2 7 5 4]
    j=4  A[j]= 6  >  x: no change             [3 1 8 6 2 7 5 4]
    j=5  A[j]= 2  <= x: i=3, swap A[i],A[j]   [3 1 2 6 8 7 5 4]
    j=6  A[j]= 7  >  x: no change             [3 1 2 6 8 7 5 4]
    j=7  A[j]= 5  >  x: no change             [3 1 2 6 8 7 5 4]
    final swap A[4] <-> A[8]                  [3 1 2 4 8 7 5 6]   q = 4

     n   sorted   n(n-1)/2   best case   (n+1)lg(n+1)-2n   random
     7       21         21          10                10       10
    15      105        105          34                34       45
    31      465        465          98                98      132
    63     1953       1953         258               258      333
   127     8001       8001         642               642      839
   255    32385      32385        1538              1538     2435
   511   130305     130305        3586              3586     4892
  1023   522753     522753        8194              8194    10637
