This is regarding the solution of the following problem "Fuzzy Sorting of Intervals"
from the book "Introduction to Algorithm"
I have found a few solutions on the internet. But have a doubt.
In all the given solutions, we are only splitting the Left partition into "Left" and "Middle" so that "Middle" overlaps with pivot element and need not be sorted.
Why do we not also split the "Right" into "Middle" and "Right" so that "Middle" overlaps with pivot and need not be sorted.
Consider a sorting problem in which the numbers are not known exactly. Instead, 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, bi], where ai ≤ bi. The goal is to fuzzy-sort these intervals, i.e., produce a permutation 〈i1, i2,..., in〉 of the intervals such that there exist cj in each [aj,bj] , satisfying c1 ≤ c2 ≤ ··· ≤ cn.
Solutions on the internet
Note to Moderator
I apologize if this question is not clear. I did not want to bloat this post. Hence I only gave the links to the actual solution at the end of the post. I was hoping people familiar with the problem will recognize it without going into the actual solution. As for my goal, it is simply to solve this problem as I am brushing up on my Algorithms.
[edit - Peter_in_2780] fixed URLs in links to solutions.[/edit]