Apply quicksort to A = { 6, 8, 2, 9, 3, 1, 5}. State the order of the data after the 2ndmedian-of-three based pivot selection as well as after the associated partitioning has taken place.

Hint: Median-of-three selection 1 produces { 5, 8, 2, 6, 3, 1, 9}where the underlined numbers are those considered. Partitioning 1 produces { 5, 3, 2, 1, 6, 8, 9 }. The number 6 is now where it needs to be. The algorithm proceeds by first processing left sublist { 5, 3, 2, 1}and then right sublist { 8, 9 }.