For the following problem, please explain (no code required) the resulting algorithm and also it's complexity:

7-6 Fuzzy sorting of intervals Consider a sorting problem in which we do not know the numbers exactly. In- stead, for each number, we know an interval on the real line to which it belongs. That is, we are given n closed intervals of the form [ai,bil, where a s bi. We wish to fuzzy-sort these intervals, i.e., to produce a permutation (i, i2, ..., in) of the intervals such that forj1,2,....n, there exist cj [ai,.bij] satisfying a. Design a randomized algorithm for fuzzy-sorting n intervals. Your algorithm should have the general structure of an algorithm that quicksorts the left end- points (the ai values), but it should take advantage of overlapping intervals to improve the running time. (As the intervals overlap more and more, the prob- lem of fuzzy-sorting the intervals becomes progressively easier. Your algorithm should take advantage of such overlapping, to the extent that it exists.) h Argue that your algorithm runs in expected time (n Ign) in general, but runs in expected time (n) when all of the intervals overlap (i.e., when there exists a value x such that x e ai, bil for all i). Your algorithm should not be checking for this case explicitly; rather, its performance should naturally improve as the amount of overlap increases