Please explain each step. Design a sorting algorithm in Python whose time complexity is as follows:

(a) when the input happens to be already non-decreasing, the algorithm takes only O(n) time;

(b) likewise, when the input happens to be already non-increasing (i.e. reverse-sorted), the algorithm takes only O(n) time;

(c) but in any other situation, the algorithm may take O(n 2 ) time. Justify that your algorithm meets these efficiency goals.