python list.sort() vs. list.sort(key=itemgetter(0))

Question

I'm a python noob, but I'm using python to solve problems on leetcode. I solved one on leetcode (merge overlapping intervals). I have the following code:

    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) < 2: return intervals
        intervals.sort(key=itemgetter(0))
        merged = [intervals[0]]
        for interval in intervals[1:]:
            if merged[-1][1] >= interval[0]: merged[-1][1] = max(merged[-1][1],interval[1])
            else: merged.append(interval)
        return merged

I noticed that if I replace intervals.sort(key=itemgetter(0)) with intervals.sort() I get noticably worse performance (~80ms vs. ~110ms respectively)

Isn't sort() technically the same as sort(key=itemgetter(0))? Shouldn't they have identical runtime? Unless, is leetcode just being inconsistent with recoding the exact runtime?

Answer 1

Your main question has been already answered.

---

LeetCode's performance measurements are not accurate at all. You can just ignore their benchmark data as you solve problems.

class Solution:
    def merge(self, intervals):
        merged = []
        for interval in sorted(intervals, key=lambda x: x[0]):
            if merged and interval[0] <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], interval[1])
            else:
                merged.append(interval)
        return merged

class Solution:
    def merge(self, intervals):
        merged = []
        for interval in sorted(intervals):
            if merged and interval[0] <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], interval[1])
            else:
                merged.append(interval)
        return merged

---

References

• For additional details, you can see the Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis^{1, 2} in there.

Answer 2

intervals.sort(key=itemgetter(0)) is different from intervals.sort(). intervals.sort(key=itemgetter(0)) only compare the first items of two intervals, but intervals.sort() compare the second when the first are same. So intervals.sort(key=itemgetter(0)) may has more intervals look the same to sort, or just do less compare when compare intervals. It maybe one reason the first one run faster.

An other possible reason is optmization. Also Python is interpreted language, the interpreter may generate biniry code when running, and do some optmization. Which one will get better performance is dependent on the interpreter.

But empirically, in most online judges, the diffrence about 30ms is just measurement error. Try again you may get a different result.