Consider a sorting problem in which the numbers are not known exactly. Instead, each element of the input sequence is a closed interval on the real line of the form 4 [ai,bi], where aibi. The goal is to fuzzysort these intervals, that is produce a permutation i1,i2,,in of the intervals such that cj[aij,bij] satisfying c1c2cn. Note, the neighboring intervals may overlap. (a) Design the fuzzysort algorithm for sorting n intervals. fuzzysort should have the general structure of quicksort working on the left endpoints of the intervals (the ai 's). but should take advantage of overlapping intervals to improve the running time. The larger are the overlaps the easier the problem becomes. Your proposed solution should take advantage of such overlaps, when they exist. (b) Show that your algorithm has expected runtime (nlogn) but runs in expected (n) when all of the intervals overlap : when x[ai,bi]i. Do not check for this case explicitly. The performance should progressively improve as the amount of overlap increases. Consider a sorting problem in which the numbers are not known exactly. Instead, each element of the input sequence is a closed interval on the real line of the form 4 [ai,bi], where aibi. The goal is to fuzzysort these intervals, that is produce a permutation i1,i2,,in of the intervals such that cj[aij,bij] satisfying c1c2cn. Note, the neighboring intervals may overlap. (a) Design the fuzzysort algorithm for sorting n intervals. fuzzysort should have the general structure of quicksort working on the left endpoints of the intervals (the ai 's). but should take advantage of overlapping intervals to improve the running time. The larger are the overlaps the easier the problem becomes. Your proposed solution should take advantage of such overlaps, when they exist. (b) Show that your algorithm has expected runtime (nlogn) but runs in expected (n) when all of the intervals overlap : when x[ai,bi]i. Do not check for this case explicitly. The performance should progressively improve as the amount of overlap increases