Process in three phases:
Add all intervals that end before the new interval starts
Merge all intervals that overlap with the new interval
Add all intervals that start after the new interval ends
function insertInterval(intervals, newInterval)
result := []
i := 0
// Phase 1: intervals ending before new starts
while i < n and intervals[i].high < newInterval.low
result.add(intervals[i])
i := i + 1
// Phase 2: merge overlapping
while i < n and intervals[i].low <= newInterval.high
newInterval.low := min(newInterval.low, intervals[i].low)
newInterval.high := max(newInterval.high, intervals[i].high)
i := i + 1
result.add(newInterval)
// Phase 3: intervals starting after new ends
while i < n
result.add(intervals[i])
i := i + 1
return result