Merge Intervals

It is quite similar to the question "Insert Interval". What we care is to merge intervals to get minimum number of intervals. For this question, we sort all the intervals first, by the value of start attribute. Then merge each interval with its neighborhood.

Code_Ganker's algorithm is almost the same:

http://blog.csdn.net/linhuanmars/article/details/21857617

He applies Comparator to take use of Collections.sort(), which is a built-in implementation of Quick Sort. But to me, to refresh Quick Sort, I implement it by myself. 

public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if(intervals == null) return null;
        if(intervals.size() <= 1) return intervals;
   
        sortByStart(intervals,0,intervals.size() - 1);// sort by the start value of each interval using quick
                                                                            //sort
        int i = 0;
       
        while(i < intervals.size() - 1){// merge each interval with its neighborhood
            if(intervals.get(i).end < intervals.get(i+1).start){
                i++;
            }
            else{
                if(intervals.get(i).end < intervals.get(i+1).end){
                    Interval tmp = new Interval(intervals.get(i).start, intervals.get(i+1).end);
                    intervals.set(i+1,tmp);
                    intervals.remove(i);
                }
                else{
                    intervals.remove(i+1);                   
                }
            }
        }
       
       
        return intervals;
    }
   
    public void sortByStart(List<Interval> intervals, int low, int up){
        int index = partition(intervals, low, up);
       
        if(index - 1 > low ){
            sortByStart(intervals,low,index - 1);
        }
        if(index < up){
            sortByStart(intervals,index,up);
        }
    }
   
    public int partition(List<Interval> intervals, int low, int up){
        int mid = (low + up)/ 2;
        int midVal = intervals.get(mid).start;
        while(low <= up){
            while(intervals.get(low).start < midVal ){
                low++;
            }
           
            while(intervals.get(up).start > midVal){
                up--;  
            }
            if(low <= up){// swap
                Interval tmpInterval = intervals.get(low);
                // int tmpEnd = inervals.get(low).end;
                intervals.set(low,intervals.get(up));
                intervals.set(up,tmpInterval);
                low++;
                up--;
            }
        }
        return low;
    }
}