Problem:
Question -State the tree (insertion) sort, odd-even transposition sort, and quick sort algorithms in 3-4 sentences each, and estimate, with suitable but brief justification, their
(i) Average case time complexities and
(ii) Their worst-case space complexities. Use known properties of binary search trees in case of tree sort and intuitive arguments about the other two to justify average case scenarios.
Please give the description of insertion sort with the help of example.