Choosing a median will not always give O(nlogn) T.C.

**Example** :-

$\rightarrow$ Suppose we have array ${\color{Red} 4}_{0},{\color{Blue} 2}_{1},{\color{Orange} 1}_{2},{\color{Brown} 3}_{3},5_{4}$

$\rightarrow$ where subscript denotes its position in the array.

Partition algo puts elements less than pivot on LHS of pivot and elements greater than equal to pivot on RHS of pivot.

$\rightarrow$ eg:-${\color{Red} 4}_{0}$ represents that $ \color{Red} 4$ is at index 0 of the array.

$\rightarrow$ At first we select ${\color{Orange} 1}_{2}$ as pivot so after running partition algo ${\color{Orange} 1}$ comes in $0^{th}$ index of array.

$\rightarrow$ Now the array becomes ${\color{Orange} 1}_{0}(sorted) ,{\color{Red} 4}_{1},{\color{Blue} 2}_{2},{\color{Brown} 3}_{3},5_{4},$

$\rightarrow$ we select ${\color{Blue} 2}_{2}$ as pivot so after running partition algo ${\color{Blue} 2}$ comes in $1^{st}$ index of array.

$\rightarrow$Now the array becomes ${\color{Orange} 1}_{0}(sorted) ,{\color{Blue} 2}_{1}(sorted),{\color{Red} 4}_{2},{\color{Brown} 3}_{3},5_{4}$

$\rightarrow$ we select ${\color{Brown} 3}_{3}$ as pivot so after running partition algo ${\color{Brown} 3}$ comes in $2^{nd}$ index of array.

$\rightarrow$Now the array becomes ${\color{Orange} 1}_{0}(sorted) ,{\color{Blue} 2}_{1}(sorted),{\color{Brown} 3}_{2}(sorted),{\color{Red} 4}_{3},5_{4}$

$\rightarrow$ we select ${\color{Red} 4}_{3}$ as pivot so after running partition algo ${\color{Red} 4}$ comes in $3^{rd}$ index of array.

$\rightarrow$Now the array becomes ${\color{Orange} 1}_{0}(sorted) ,{\color{Blue} 2}_{1}(sorted),{\color{Brown} 3}_{2}(sorted),{\color{Red} 4}_{3}(sorted),5_{4}$

$\rightarrow$ we select $5_{4}$ as pivot so after running partition algo $5$ comes in $4^{th}$ index of array.

$\rightarrow$Now the array becomes ${\color{Orange} 1}_{0}(sorted) ,{\color{Blue} 2}_{1}(sorted),{\color{Brown} 3}_{2}(sorted),{\color{Red} 4}_{3}(sorted),5_{4}(sorted)$

$\rightarrow$ So here Partition Algo runs for $n$ times and T.C. of partition Algo is $O(n)$

$\rightarrow$ where $n\rightarrow$ number of elements in the array.

$\therefore$ Total time complexity $= n*O(n) = O(n^{2})$