fuzzy sort

All regions have intersection does not require sorting.

Solution is from here:
http://alumni.media.mit.edu/~dlanman/courses/cs157/HW3.pdf

Some explanation:
Step 1: Find-Intersection
This step is to find a region [a,b] that does not have intersection with other regions [$a_i$,$b_i$]. So this is  a minimal regions.

Step 2:  Partition-Right and Partition-Left-Middle

So the middle part does not need to sort.

Step 3: sort left part and right part.

Some wrong solution before:

get a pivot region arbitrary. and then divide the whole array as 3 parts: left, middle, right.

left part is bi less than middle and right part is ai  greater than middle. middle part is the set of regions that have intersection with the given pivot region.

The problem here is that: middle region may have two regions that are disjoint. therefore, the two regions still need sort, thus violating the fact that middle part does not require sorting. For example, the pivot regions is [5, 9] and middle part is [6,7], [8,9] and [5,9]. then [6,7] and [8,9] definitely need sort.