Short, simple, O(n), in-place, Java solution with explanation
The idea is to look at each interval in the list. If it intersects with newInterval then merge it to newInterval and delete it. In the end add newInterval back 
The idea is to look at each interval in the list. If it intersects with newInterval then merge it to newInterval and delete it. In the end add newInterval back to its corresponding place.\n\n    public class Solution {\n        public List<Interval> insert(List<Interval> intervals, Interval newInterval) {\n            ListIterator<Interval> i = intervals.listIterator();\n            Interval in;\n            while (i.hasNext()) {\n                in = i.next();\n                if (newInterval.end < in.start) {\n                    i.previous();\n                    break;\n                }\n                if (in.start <= newInterval.end && newInterval.start <= in.end) {\n                    newInterval.start = Math.min(newInterval.start, in.start);\n                    newInterval.end = Math.max(newInterval.end, in.end);\n                    i.previous();\n                    i.remove();\n                }\n            }\n            i.add(newInterval);\n            return intervals;\n        }\n    }
['Java']