Let us consider sorting problem.

$($a$)$ What is the lower bound for the sorting problem that sort by comparing values? Write an informal explanation of how it is established.

$($b$)$ What is the upper bound for a problem? Explanation of how it is established.

$($c$)$ List names of $7$ sorting algorithms. Write worst$-$case time complexity and space complexity of each. You may want to a make three$-$column table.

$($d$)$ Suppose the list above has all known sorting algorithms in the world. What is the upper bound for the sorting problem?

$($e$)$ In the list above, how many are optimal algorithm sorting? Write their names.